2023/03/31 by Yiao Ju, Ju, Yiao, Shenwei Huang +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2303.18003
openalex publication_date 2023/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we initiate a systematic study on a new notion called near optimal colourability which is closely related to perfect graphs and the Lovász theta function. A graph family G is \em near optimal colourable if there is a constant number c such that every graph G\inG satisfies χ(G)≤max\c, ω(G)\, where χ(G) and ω(G) are the chromatic number and clique number of G, respectively. The near optimal colourable graph families together with the Lovász theta function are useful for the study of the chromatic number problems for hereditary graph families. We investigate the near optimal colourability for (H1,H2)-free graphs. Our main result is an almost complete characterization for the near optimal colourability for (H1,H2)-free graphs with two exceptional cases, one of which is the celebrated Gyárfás conjecture. As an application of our results, we show that the chromatic number problem for (2K2,P4\vee Kn)-free graphs is polynomial time solvable, which solves an open problem in [K.~K.~Dabrowski and D.~Paulusma. On colouring (2P2, H)-free and (P5, H)-free graphs. Information Processing Letters, 134:35-41, 2018].