Chromatic number of \(P_5\)-free graphs: Reed's conjecture

DOI10.1016/j.disc.2015.11.020zbMath1334.05045OpenAlexW2491359957WikidataQ123231074 ScholiaQ123231074MaRDI QIDQ279215

Ingo Schiermeyer

Publication date: 27 April 2016

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

Full work available at URL: https://doi.org/10.1016/j.disc.2015.11.020

zbMATH Keywords

chromatic numberchi-binding functionP5-free graphReed's conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (15)

On the chromatic number of some \(P_5\)-free graphs ⋮ THE CHROMATIC NUMBER OF -FREE GRAPHS ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ A note on Reed's conjecture for triangle-free graphs ⋮ On the chromatic number of \(P_5\)-free graphs with no large intersecting cliques ⋮ Large cliques in graphs with high chromatic number ⋮ Divisibility and coloring of some \(P_5\)-free graphs ⋮ On the chromatic number of (P5,dart)-free graphs ⋮ 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 ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ On the chromatic number of \((P_{5},K_{2,t})\)-free graphs ⋮ On the chromatic number of (P_{5},windmill)-free graphs ⋮ Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi\)-bounded ⋮ Spectral properties of cographs andP₅-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
• The strong perfect graph theorem
• Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \)
• Dominating cliques in \(P_ 5\)-free graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• The chromatic number of \(\{P_5,K_4\}\)-free graphs
• An upper bound for the chromatic number of line graphs
• A Note On Reed's Conjecture

This page was built for publication: Chromatic number of \(P_5\)-free graphs: Reed's conjecture