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.

اخر الاخبار

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

مجلة تسليم تدعو الباحثين والأكاديميين للمشاركة في أعدادها القادمة

المجمع العلمي يواصل إقامة محاضراته الأسبوعية في مقام الإمام المهدي (عجل الله فرجه)

جامعة الكفيل تطلق الدورة التدريبية الصيفية لطلبة كلية الهندسة التقنية

استعدادًا لزيارة الأربعين العتبة العباسية المقدسة تعقد الورشة التنسيقية الرابعة الخاصة بمراكز إرشاد التائهين

المزيد

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

دراسة علمية تكشف مفاجأة حول الأسباب الحقيقية للسمنة

دراسة: الأطباء يتجاهلون "سببا شائعا" لارتفاع ضغط الدم

نظامك الغذائي غني بالبروتين؟.. احذر هذه الآثار الجانبية

لا تتجاهلها.. أعراض تنذرك بأنك مهدد بالإصابة بالسكري

المزيد

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

ISOFIX: معيار الأمان الذهبي لمقاعد الأطفال في السيارات

هل المحرك الأكبر دائمًا الأفضل للسيارة؟

اختبارات ناجحة لمحرك "VK-800" الروسي وتطويره لطائرة بايكال الخفيفة

رئيس إنفيديا: الذكاء الاصطناعي الصيني "محفز للتقدم العالمي"

المزيد

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

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