Coloring (gem, co‐gem)‐free graphs. Issue 3 (12th April 2018) - Karthick, T.; Maffray, Frédéric
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 ) .