Homogeneous sets, clique-separators, critical graphs, and optimal X -binding functions

Given a set H of graphs, let f(H)* : N(>)0 -> N(>)0 be the optimal chi-binding function of the class of H-free graphs, that is, f(H)*(omega) = max{chi(G) : G is H-free, omega(G) = omega}. In this paper, we combine the two decomposition methods by homogeneous sets and clique-separators in order to determine optimal chi-binding functions for subclasses of P-5-free graphs and of (C-5 , C-7, ...)-free graphs. In particular, we prove the following for each omega >= 1: (i) f*({P5,banner})(omega )= f *({3K1})(omega) is an element of Theta(omega(2)/ log(omega)), ii) f*({P5,banner})(omega )= f *({2K2})(omega) is an element of O(omega(2)), iii) f*({C5,C7, ..., banner}) (omega) = f *({c5, 3K1}) (omega) is not an element of O (omega), and. iv) f *({P5,C4}) (omega) = [(5 omega - 1)/4]. We also characterise, for each of our considered graph classes, all graphs G with chi(G) > chi(G - u) for each u is an element of V (G). From these structural results, Reed's conjecture relating chromatic number, clique number, and maximum degree of a graph - follows for (P-5, banner)-free graphs. (C) 2022 Published by Elsevier B.V.

Automated summary

In this paper, the optimal chi-binding functions for subclasses of P-5-free graphs and (C-5, C-7, ...)-free graphs are determined using a combination of decomposition methods. Several conclusions are derived, including the verification of Reed's conjecture for (P-5, banner)-free graphs.