The chromatic number of \(\{P_5,K_4\}\)-free graphs

DOI10.1016/j.disc.2012.12.019zbMath1260.05056OpenAlexW2580169513MaRDI QIDQ1942664

Frédéric Maffray, Louis Esperet, Grégory Morel, Laetitia Lemoine

Publication date: 19 March 2013

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

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

zbMATH Keywords

coloring\(P_{5}\)-free

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Related Items (21)

Chromatic number of \(P_5\)-free graphs: Reed's conjecture ⋮ On the chromatic number of \(2 K_2\)-free graphs ⋮ On the chromatic number of some \(P_5\)-free graphs ⋮ On the chromatic number of (\(P_6\), diamond)-free graphs ⋮ On the chromatic number of \(P_5\)-free graphs with no large intersecting cliques ⋮ 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 ⋮ On the chromatic number of (P5,dart)-free graphs ⋮ Coloring (\(P_5\), kite)-free graphs with small cliques ⋮ Graphs of large chromatic number ⋮ A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ 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 ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ On indicated coloring of some classes of graphs ⋮ $(2P_2,K_4)$-Free Graphs are 4-Colorable ⋮ Coloring of \((P_5, 4\)-wheel)-free graphs

This page was built for publication: The chromatic number of \(\{P_5,K_4\}\)-free graphs