Graph Hole

Chvátal defines the term hole to mean "a chordless cycle of length at least four." The restriction "of length at least four" allows use of the term "hole" regardless of if the definition of "chordless cycle" is taken to already exclude cycles of length 3 (e.g., West 2002, p. 225) or to include them (Cook 2012, p. 197; Wikipedia).

Graph holes are called even if they have an even number of vertices and odd if they have an odd number of vertices. The graph complement of a hole is called a graph antihole. No odd hole is a perfect graph (since the clique number of an odd hole is 2 and its chromatic number is 3).

---

REFERENCES

Chvátal, V. "The Strong Perfect Graph Theorem." http://www.cs.concordia.ca/~chvatal/perfect/spgt.html.

Cook, K.; Eschen, E. M.; Sritharan, R.; and Wang, X. "Completing Colored Graphs to Meet a Target Property." In Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers.

Ed. A. Brandstädt, K. Jansen, and R. Reischuk). Berlin, Germany:ÊSpringer, pp. 189-200, 2013.

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 225, 2000.

Wikipedia contributors. "Induced Path." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia. Aug. 7, 2020; retreived Sep. 4, 2020. https://en.wikipedia.org/wiki/Induced_path.

اخر الاخبار

اخبار العتبة العباسية المقدسة

العتبة العباسية المقدسة تنظّم مسيرات عزائية لإحياء ذكرى عاشوراء في نينوى

قسم الشؤون الفكرية يحيي ذكرى استشهاد الإمام الحسين (عليه السلام) في القارة الإفريقية

قسمُ التربية والتعليم يقيم مجلسه العزائي السنوي بذكرى عاشوراء

معهد القرآن الكريم النسوي يُقيم مجلس عزاء حسيني إحياءً لذكرى عاشوراء

المزيد

الآخبار الصحية

تناول الجبن.. مفيد للجسم أم خطر يهدد صحتك؟

طبيبة أسنان تحذر.. لا تتجاهل هذه العلامة بعد التنظيف

يجب أن تأكل المزيد من الشمام هذا الصيف.. إليك السبب ؟

تأثير صحي كبير.. كم بيضة يجب أن تتناول يوميا؟

المزيد

الآخبار التكنلوجية

أداء خلايا البيروفسكايت الشمسية تحت الماء قد يزيد كفاءة تحويل الكهرباء

مسافة الأمان: أساس القيادة الآمنة وتجنب الحوادث

هل القيادة السريعة تعني استهلاك اكثر للوقود؟

لماذا يعتبر كوكب المريخ غير صالح للحياة؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength