2024/09/11 by Chen, Ran, Xu, Baogang · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.06944
A class \cal G of graphs is χ-\em polydet if \cal G has a polynomial binding function f and there is a polynomial time algorithm to determine an f(ω(G))-coloring of G∈ \cal G. Let Pt and Ct denote a path and a cycle on t vertices, respectively. A \em bull consists of a triangle with two disjoint pendant edges, a \em hammer is obtained by identifying an end of P3 with a vertex of a triangle, a \em fork+ is obtained from K1, 3 by subdividing an edge twice. Let H be a bull or a hammer, and F be a P7 or a fork+. We determine all (C3, C4, F)-free graphs without clique cutsets and universal cliques, and present a close relation between (C4, F, H)-free graphs and the Petersen graph. As a consequence, we show that the classes of (C4, F, H)-free graphs are χ-polydet with nearly optimal linear binding functions.