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

DOI10.1016/J.DISC.2022.112795zbMATH Open1484.05063arXiv2004.01365OpenAlexW4205424725MaRDI QIDQ2113346FDOQ2113346

Authors: Arnab Char, T. Karthick 

Publication date: 14 March 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

vertex coloring\(P_5\)-free graphs\(\chi\)-boundednesswheel-free graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (17)

• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
• Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs
• A bound for the chromatic number of \((P_5, \text{gem})\)-free graphs
• Coloring (\(P_5\), kite)-free graphs with small cliques
• Title not available (Why is that?)
• THE CHROMATIC NUMBER OF -FREE GRAPHS
• Excluding 4-wheels
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions
• The chromatic number of (\(P_5\), HVN)-free graphs
• 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
• On graphs with no induced five‐vertex path or paraglider
• Coloring graphs with no induced five‐vertex path or gem
• A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs
• Divisibility and coloring of some \(P_5\)-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)