Structure and coloring of some (\(P_7,C_4\))-free graphs

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-02
Main Authors: Chen, Ran, Wu, Di, Xu, Baogang
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 (\romannumeral 1) \(\chi (G)\leq \max\{3,\omega(G)\}\) if \(G\) is \((P_7, C_4,\) diamond)-free, (\romannumeral 2) \(\chi(G)\leq \omega(G)+1\) if \(G\) is \((P_7, C_4,\) kite)-free and (\romannumeral 3) \(\chi(G)\leq 2\omega(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}.
ISSN:2331-8422