UP - logo
E-resources
Full text
Peer reviewed
  • Structure of some ( P7, C4)...
    Chen, Ran; Wu, Di; Xu, Baogang

    Discrete Applied Mathematics, 11/2024, Volume: 357
    Journal Article

    We use Pt and Ct to denote a path and a cycle on t vertices, respectively. A diamond is a graph obtained from two triangles that share exactly one edge. A kite is a graph that consists of a diamond and another vertex adjacent to a vertex of degree 2 of the diamond. A gem is a graph that consists of a P4 plus a vertex adjacent to all vertices of the P4. Choudum et al. (2021) proved that every (P7,C7,C4, gem)-free graph has either a clique cutset or a vertex whose neighbors is the union of two cliques unless it is a clique blowup of the Petersen graph, and every non-Petersen (P7,C7,C4, diamond)-free graph has either a clique cutset or has a vertex of degree at most max{2,ω(G)−1}. In this paper, we extend these two results respectively to (P7,C4, gem)-free graphs and (P7,C4, diamond)-free graphs. We also prove that if G is a (P7,C4, kite)-free graph with δ(G)≤ω(G) and without clique cutsets, then there is an integer ℓ≥0 such that G=Kℓ+H, where H is either the Petersen graph or a well-defined graph F. This implies a polynomial algorithm which can determine the chromatic number of (P7,C4, diamond)-free graphs, color (P7,C4, kite)-free graphs G with (ω(G)+1) colors, and color (P7,C4, gem)-free graphs G with (2ω(G)−1) colors.