Coloring graphs with no induced five‐vertex path or gem

DOI10.1002/jgt.22572zbMath1525.05047arXiv1810.06186OpenAlexW3023691192MaRDI QIDQ6134643

T. Karthick, Frédéric Maffray, Maria Chudnovsky, Peter Maceli

Publication date: 22 August 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberclique number\(\chi\)-boundedness\(\mathrm{P}_5\)-free graphs

Mathematics Subject Classification ID

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

Related Items (13)

Colouring graphs with no induced six-vertex path or diamond ⋮ On the chromatic number of some \(P_5\)-free graphs ⋮ Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions ⋮ A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs ⋮ Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors ⋮ On graphs with no induced five‐vertex path or paraglider ⋮ On the chromatic number of \(P_5\)-free graphs with no large intersecting cliques ⋮ Divisibility and coloring of some \(P_5\)-free graphs ⋮ Some results on \(k\)-critical \(P_5\)-free graphs ⋮ Coloring (\(P_5\), kite)-free graphs with small cliques ⋮ A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs ⋮ Colouring graphs with no induced six-vertex path or diamond ⋮ Coloring of \((P_5, 4\)-wheel)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Chromatic number of \(P_5\)-free graphs: Reed's conjecture
• The strong perfect graph theorem
• Coloring the hypergraph of maximal cliques of a graph with no long path
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• On the structure of (\(P_{5}\),\,gem)-free graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Graph Theory and Probability. II
• Perfect coloring and linearly χ-boundP6-free graphs
• Coloring (gem, co‐gem)‐free graphs
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• Square-Free Graphs with No Six-Vertex Induced Path
• A BOUND FOR THE CHROMATIC NUMBER OF (, GEM)-FREE GRAPHS
• Perfect divisibility and 2‐divisibility

This page was built for publication: Coloring graphs with no induced five‐vertex path or gem