Improved bounds on the chromatic number of (P5, flag)-free graphs

Given a positive integer t, let Pt and Kt respectively denote the chordless path and the complete graph on t vertices. For a graph G, let chi(G) and w(G) respectively denote the chromatic number and clique number of G. It is known that every (P5, K4)-free graph G satisfies chi (G) <= 5, and the bound is tight. A flag is the graph obtained from a K4 by attaching a pendent vertex. Clearly, the class of flag-free graphs generalizes the class of K4-free graphs. In this paper, we show the following: center dot Every (P5, flag, K5)-free graph G that contains a K4 satisfies chi (G) <= 8. center dot Every (P5, flag, K6)-free graph G satisfies chi(G) <= 8. center dot Every (P5, flag, K7)-free graph G satisfies chi(G) <= 9. We also give examples to show that the given bounds are tight. Further, we show that every (P5, flag)-free graph G with w(G) >= 4 satisfies chi(G) <= max{8, 2w(G) - 3}, and the bound is tight for w(G) is an element of {4, 5, 6}. We note that our bound is an improvement over that given in Dong et al. [3,4].(c) 2023 Elsevier B.V. All rights reserved.

Automated summary

This study discovers that for graphs G that do not contain specified structures, if G contains K4, then the chromatic number chi(G) does not exceed 8; if G does not contain K4 but contains a variant of K4 called flag, then chi(G) does not exceed 9. Examples with tight bounds are also provided. Furthermore, for graphs G that do not contain the specified structure flag, with the condition w(G) >= 4, it is shown that chi(G) does not exceed max{8, 2w(G) - 3}, and the bound is tight when w(G) is 4, 5, or 6. Compared to previous literature, this study proposes better bounds.