2023/05/28 by Chen, Ran, Xu, Baogang
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2305.17745
Let Pt and Ct be a path and a cycle on t vertices, respectively. In 2021, Choudum \em et al. [Disc. Math. 344 (2021) 112244] determined the structures of (P7,C7,C4, diamond)-free and (P7,C7,C4, gem)-frees, and gave correspondingly tight upper bounds to the chromatic numbers of these graphs. In this paper, we study the structure of (P7, C5, kite, paraglider)-free graphs, which is a superfamily of (P7, C5, diamond)-free graphs. We show that there is a unique connected imperfect (P7, C5, kite, paraglider)-free graph with δ(G)≥ω(G)+1, which has no clique cutsets, no universal cliques, and no pair of vertices of which one's neighborhoods contains the other's. As a consequence, we show that (P7, C5, kite, paraglider)-free graphs are χ-polydet with a binding function ω(G)+1. Where a \em diamond (resp. \em gem) consists of a P3 (resp. P4) and a new vertex adjacent to all vertices of the P3 (resp. P4), a \em kite consists of a P4 and a new vertex adjacent to consecutive three vertices of the P4, and a \em paraglider consists of a C4 and a new vertex adjacent to three vertices of the C4.