Strengthening Brooks' chromatic bound on P₆-free graphs

DOI10.1016/J.DAM.2023.09.031MaRDI QIDQ6143873zbMATH OpenOpenAlexFDO

Authors Uttam K. Gupta, D. Pradhan

Publication date 24 January 2024

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

Full work available at URL https://doi.org/10.1016/j.dam.2023.09.031

zbMATH Keywords

\( ( P_5, C_5 )\)-free graphs\( ( P_6, C_4 )\)-free graphsBorodin-Kostochka conjecturegraph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs
• Borodin-Kostochka's conjecture on \(\{P_2 \cup P_3, C_4\}\)-free graphs
• Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
• An optimal χ‐bound for (P6, diamond)‐free graphs
• Borodin-Kostochka conjecture holds for \(\overline{K_{1 , 3}} \)-free graphs

Cites work

• A strengthening of Brooks' theorem
• Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs
• Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
• Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
• Coloring Claw-Free Graphs with \Delta-1 Colors
• Coloring the hypergraph of maximal cliques of a graph with no long path
• Constructions of k-critical P₅-free graphs
• scientific article; zbMATH DE number 3719178 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Improvement on Brooks' chromatic bound for a class of graphs
• Linearly \(\chi \)-bounding \((P_6, C_4)\)-free graphs
• Note on the colouring of graphs
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Paw-free graphs
• Ramsey-type theorems
• The chromatic number of graphs which induce neither \(K_{1,3}\) nor \(K_ 5-e\)
• The strong perfect graph theorem

Cited in

(3)

• Coloring hammer-free graphs with \(\Delta - 1\) colors
• The chromatic number of \(\{P_2 \cup P_3,\text{ banner}\}\)-free graphs
• On the chromatic number of \(\{\text{bull, diamond}\}\)-free graphs

This page was built for publication: Strengthening Brooks' chromatic bound on \(P_6\)-free graphs

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