Structure and coloring of ($P_7$, $C_5$, diamond)-free graphs

arXiv2305.17745MaRDI QIDQ6438268

Ran Chen, Baogang Xu

Publication date: 28 May 2023

Abstract: We use $P_t$ and $C_t$ to denote a path and a cycle on t vertices, respectively. A diamond consists of two triangles that share exactly one edge, a kite is a graph obtained from a diamond by adding a new vertex adjacent to a vertex of degree 2 of the diamond, a paraglider is the graph that consists of a $C_4$ plus a vertex adjacent to three vertices of the $C_4$, a paw is a graph obtained from a triangle by adding a pendant edge. A comparable pair $(u,v)$ consists of two nonadjacent vertices $u$ and $v$ such that $N(u)subseteqN(v)$ or $N(v)subseteqN(u)$. A universal clique is a clique $K$ such that $xyinE(G)$ for any two vertices $xinK$ and $yinV(G)setminusK$. A blowup of a graph H is a graph obtained by substituting a stable set for each vertex, and correspondingly replacing each edge by a complete bipartite graph. We prove that 1) there is a unique connected imperfect $(P_7,C_5$, kite, paraglider)-free graph G with delta(G) geq omega(G)+ 1 which has no clique cutsets, no comparable pairs, and no universal cliques; 2) if G is a connected imperfect $(P_7,C_5$, diamond)-free graph with delta(G) geq max{3, omega(G)} and without comparable pairs, then G is isomorphic to a graph of a well defined 12 graph families; and 3) each connected imperfect $(P_7,C_5$, paw)-free graph is a blowup of $C_7$. As consequences, we show that chi(G) leq omega(G)+1 if G is (P7, C5, kite, paraglider)-free, and chi(G) leq max{3, omega(G)} if G is $(P_7,C_5$, H)-free with H being a diamond or a paw. We also show that chi(G) leq

This page was built for publication: Structure and coloring of ($P_7$, $C_5$, diamond)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6438268)