Structure and coloring of some (P₇,C₄)-free graphs

arXiv2302.11115MaRDI QIDQ6427239FDOQ6427239

Authors: Ran Chen, Di Wu, Baogang Xu 

Publication date: 21 February 2023

Abstract: Let $G$ be a graph. We use $P_t$ and $C_t$ to denote a path and a cycle on $t$ vertices, respectively. A {em diamond} is a graph obtained from two triangles that share exactly one edge. A {em kite} is a graph consists of a diamond and another vertex adjacent to a vertex of degree 2 of the diamond. A {em gem} is a graph that consists of a $P_4$ plus a vertex adjacent to all vertices of the $P_4$. In this paper, we prove some structural properties to $(P_7,C_4,$ diamond)-free graphs, $(P_7,C_4,$ kite)-free graphs and $(P_7,C_4,$ gem)-free graphs. As their corollaries, we show that ( omannumeral 1) $chi(G)leqmax3,omega(G)$ if $G$ is $(P_7,C_4,$ diamond)-free, ( omannumeral 2) $chi(G)leqomega(G)+1$ if $G$ is $(P_7,C_4,$ kite)-free and ( omannumeral 3) $chi(G)leq2omega(G)-1$ if $G$ is $(P_7,C_4,$ gem)-free. These conclusions generalize some results of Choudum {em et al} and Lan {em et al}.

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

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