Coloring (gem,  co‐gem)‐free graphs. Issue 3 (12th April 2018)

• Record Type: Journal Article
• Authors: Karthick, T.; Maffray, Frédéric
• Is Part Of: Journal of graph theory. Volume 89:Issue 3(2018)
• Page Start: 288
• Page End: 303
• Publication Date: 2018-04-12
• Subjects: χ‐boundedness -- chromatic number -- clique size -- degree; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22251
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A gem is a graph that consists of a path on four vertices plus a vertex adjacent to all four vertices of the path. A co‐gem is the complement of a gem. We prove that every (gem, co‐gem)‐free graph G satisfies the inequality χ ( G ) ≤ ⌈ 5 ω ( G ) 4 ⌉ (a special case of a conjecture of Gyárfás) and the inequality χ ( G ) ≤ ⌈ Δ ( G ) + ω ( G ) + 1 2 ⌉ (a special case of a conjecture of Reed). Moreover, we give an O ( n 3 ) ‐time algorithm that computes the chromatic number of any (gem, co‐gem)‐free graph with n vertices, while the existing algorithm in the literature takes O ( n 2 17 + 1 ) .