On the chromatic number of some \(P_5\)-free graphs

DOI10.1016/J.DISC.2022.113004zbMath1491.05075arXiv2202.13177OpenAlexW4226124603MaRDI QIDQ2144602

Yian Xu, Wei Dong, Bao-Gang Xu

Publication date: 14 June 2022

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

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

zbMATH Keywords

chromatic numberinduced subgraph\( P_5\)-freeperfect divisibility

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (6)

Coloring of some crown-free graphs ⋮ Coloring graphs without induced \(P_5\) or \(K_5-e\) ⋮ Improved bounds on the chromatic number of (\(P_5\), flag)-free graphs ⋮ Divisibility and coloring of some \(P_5\)-free graphs ⋮ Coloring of a superclass of \(2K_2\)-free graphs ⋮ A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chromatic number of \(P_5\)-free graphs: Reed's conjecture
• On the chromatic number of \((P_{5},K_{2,t})\)-free graphs
• The strong perfect graph theorem
• A bound on the chromatic number of graphs without certain induced subgraphs
• Dominating cliques in \(P_ 5\)-free graphs
• On the chromatic number of \(2 K_2\)-free graphs
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Vertex colouring and forbidden subgraphs -- a survey
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• The chromatic number of \(\{P_5,K_4\}\)-free graphs
• Graph Theory and Probability
• Perfect coloring and linearly χ-boundP6-free graphs
• On the structure of (banner, odd hole)‐free graphs
• On the chromatic number of (P_{5},windmill)-free graphs
• A survey of χ‐boundedness
• A BOUND FOR THE CHROMATIC NUMBER OF (, GEM)-FREE GRAPHS
• Perfect divisibility and 2‐divisibility
• On graphs with no induced five‐vertex path or paraglider
• Coloring graphs with no induced five‐vertex path or gem

This page was built for publication: On the chromatic number of some \(P_5\)-free graphs