Coloring graphs with no induced five‐vertex path or gem

DOI10.1002/JGT.22572MaRDI QIDQ6134643zbMATH OpenOpenAlexFDO

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)

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)

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.

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

Cites work

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

Cited in

(18)

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

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)