Coloring of (P₅, 4-wheel)-free graphs

DOI10.1016/J.DISC.2022.112795MaRDI QIDQ2113346zbMATH OpenOpenAlexFDO

Authors Arnab Char, T. Karthick

Publication date 14 March 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.01365

zbMATH Keywords

\(\chi\)-boundedness\(P_5\)-free graphsvertex coloringwheel-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Abstract: For a graph $G$, $chi(G)$ $(omega(G))$ denote its chromatic (clique) number. A $P_5$ is the chordless path on five vertices, and a $4$-$wheel$ is the graph consisting of a chordless cycle on four vertices $C_4$ plus an additional vertex adjacent to all the vertices of the $C_4$. In this paper, we show that every ($P_5$, $4$-wheel)-free graph $G$ satisfies $chi(G)leqfrac32omega(G)$. Moreover, this bound is almost tight. That is, there is a class of ($P_5$, $4$-wheel)-free graphs $calL$ such that every graph $HincalL$ satisfies $chi(H)geqfrac107omega(H)$. This generalizes/improves several previously known results in the literature.

Review text

A hereditary (i.e. closed under taking subgraphs) family \(\mathcal{C}\) of graphs has a \(\chi\)-binding function \(f\) if, for any \(G \in \mathcal{C}\), it holds that \(\chi(G) \leq f(\omega(G))\). Here, \(\chi(G)\) and \(\omega(G)\) are the chromatic number of \(G\) and the clique number of \(G\) (the size of a maximum clique of \(G\)) respectively. The article provides a new \(\chi\)-binding function for the family of \((P_5, W_4)\)-free graphs. Here, \(P_5\) is the path on five vertices, and \(W_4\) is the \(4\)-wheel, the graph obtained from a cycle on \(4\) vertices after adding a new vertex adjacent to all the vertices of the cycle; and a graph is \((P_5, W_4)\)-free if it does not contain any of \(P_5\) or \(W_4\) as induced subgraphs. The main result of the paper says that for any \((P_5, W_4)\)-free graph \(G\), it holds that \(\chi(G) \leq 3 \omega(G)/2\) (or equivalently, \(f(x) = 3x/2\) is a \(\chi\)-binding function for the family of \((P_5, W_4)\)-free graphs). This is the best \(\chi\)-binding function for the family \((P_5, W_4)\)-free graphs known so far. It also provides better \(\chi\)-binding functions for families of graphs where \(\chi\)-binding functions were already known, e.g. for the family of \((3 K_1, W_4)\)-free graphs [\textit{S. A. Choudum} et al., Graphs Comb. 24, No. 5, 413--428 (2008; Zbl 1190.05066)]. The main result is also complemented with examples of \((P_5, W_4)\)-free graphs \(G\) which satisfy \(\chi(G) \geq 10 \omega(G)/7\). The proof follows from a structural description of \((P_5, W_4)\)-free graphs, which is the main technical result of the paper. An atom is a graph without a clique cutset (a clique whose removal increases the number of connected components). A quasi-line graph is a graph \(G\) where the neighbourhood \(N(v)\) of any vertex \(v \in V(G)\) can be expressed as the union of two cliques. A graph \(G\) is said to be nice if there exist three stable sets (independent sets) \(S_1\), \(S_2\), \(S_3\) whose removal decreases the clique number of \(G\) by at least \(2\). The main structural result claims that any connected \((P_5, W_4)\)-free atom \(G\) must be a perfect graph, a nice graph, or a quasi-line graph.

Recommendations

• A bound for the chromatic number of \((P_5, \text{gem})\)-free graphs
• Improved bounds on the chromatic number of (\(P_5\), flag)-free graphs
• Perfect coloring and linearly χ-boundP6-free graphs
• On the chromatic number of some \(P_5\)-free graphs
• The chromatic number of \(\{P_5,K_4\}\)-free graphs

Cites work

• \(\chi\)-bounds, operations, and chords
• A survey of -boundedness
• Chromatic bounds for some classes of 2 K₂-free graphs
• Coloring graphs with no induced five‐vertex path or gem
• Coloring quasi-line graphs
• Coloring the hypergraph of maximal cliques of a graph with no long path
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs
• On graphs with no induced five‐vertex path or paraglider
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• On the chromatic number of (P_{5},windmill)-free graphs
• Perfect coloring and linearly χ-boundP6-free graphs
• Perfect divisibility and 2‐divisibility
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Square-Free Graphs with No Six-Vertex Induced Path
• Substitution and \(\chi\)-boundedness
• The chromatic number of \(\{P_5,K_4\}\)-free graphs
• The class of \((P_7, C_4, C_5)\)-free graphs: decomposition, algorithms, and \(\chi \)-boundedness
• The strong perfect graph theorem

Cited in

(20)

• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs
• Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions
• A tight linear bound to the chromatic number of (P₅, K₁ +(K₁ K₃))-free graphs
• scientific article; zbMATH DE number 2186978 (Why is no real title available?)
• A bound for the chromatic number of \((P_5, \text{gem})\)-free graphs
• Excluding 4-wheels
• THE CHROMATIC NUMBER OF -FREE GRAPHS
• On graphs with no induced five‐vertex path or paraglider
• Coloring graphs without induced \(P_5\) or \(K_5-e\)
• Improved bounds on the chromatic number of (\(P_5\), flag)-free graphs
• On cd-coloring of \(\{P_5,K_4\}\)-free chordal graphs
• Divisibility and coloring of some \(P_5\)-free graphs
• Coloring graphs with no induced five‐vertex path or gem
• Coloring (P₅, kite)-free graphs with small cliques
• The chromatic number of (\(P_5\), HVN)-free graphs
• Improved bounds on the chromatic number of (P₃ p₂, W₄)-free graphs
• On graphs with no induced P₅ or K₅-e
• -boundedness and related problems on graphs without long induced paths: a survey
• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs

This page was built for publication: Coloring of \((P_5, 4\)-wheel)-free graphs

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