Coloring graphs with no induced five‐vertex path or gem

DOI10.1002/JGT.22572zbMATH Open1525.05047arXiv1810.06186OpenAlexW3023691192MaRDI QIDQ6134643FDOQ6134643

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

Publication date: 22 August 2023

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

Abstract: For a graph $G$, let $chi(G)$ and $omega(G)$ respectively denote the chromatic number and clique number of $G$. We give an explicit structural description of ($P_5$,gem)-free graphs, and show that every such graph $G$ satisfies $chi(G)lelceilfrac5omega(G)4ceil$. Moreover, this bound is best possible.

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

Recommendations

• A bound for the chromatic number of \((P_5, \text{gem})\)-free graphs
• Coloring (gem, co‐gem)‐free graphs
• Coloring of \((P_5, 4\)-wheel)-free graphs
• On the structure of (\(P_{5}\),\,gem)-free graphs
• On the chromatic number of some \(P_5\)-free graphs

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)

Cites Work

• Title not available (Why is that?)
• The strong perfect graph theorem
• Title not available (Why is that?)
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Chromatic number of \(P_5\)-free graphs: Reed's conjecture
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• Perfect coloring and linearly χ-boundP6-free graphs
• Graph Theory and Probability. II
• Coloring the hypergraph of maximal cliques of a graph with no long path
• On the structure of (\(P_{5}\),\,gem)-free graphs
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Coloring (gem, co‐gem)‐free graphs
• Square-Free Graphs with No Six-Vertex Induced Path
• Perfect divisibility and 2‐divisibility
• A bound for the chromatic number of \((P_5, \text{gem})\)-free graphs

Cited In (18)

• Graphs with No Induced Five‐Vertex Path or Antipath
• On the chromatic number of some \(P_5\)-free graphs
• Coloring of \((P_5, 4\)-wheel)-free graphs
• Perfect coloring and linearly χ-boundP6-free graphs
• A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
• Colouring graphs with no induced six-vertex path or diamond
• Colouring graphs with no induced six-vertex path or diamond
• Coloring (\(P_5\), kite)-free graphs with small cliques
• Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions
• The chromatic number of (\(P_5\), HVN)-free graphs
• Coloring (gem, co‐gem)‐free graphs
• Coloring graphs without induced \(P_5\) or \(K_5-e\)
• Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
• Some results on \(k\)-critical \(P_5\)-free graphs
• On the chromatic number of \(P_5\)-free graphs with no large intersecting cliques
• On graphs with no induced five‐vertex path or paraglider
• 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 graphs with no induced five‐vertex path or gem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134643)