Strengthening Brooks' chromatic bound on \(P_6\)-free graphs
From MaRDI portal
Publication:6143873
DOI10.1016/j.dam.2023.09.031OpenAlexW4387442057MaRDI QIDQ6143873
Dinabandhu Pradhan, Uttam K. Gupta
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
graph coloringBorodin-Kostochka conjecture\( ( P_5, C_5 )\)-free graphs\( ( P_6, C_4 )\)-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
- Ramsey-type theorems
- The strong perfect graph theorem
- The chromatic number of graphs which induce neither \(K_{1,3}\) nor \(K_ 5-e\)
- Paw-free graphs
- Improvement on Brooks' chromatic bound for a class of graphs
- On an upper bound of the graph's chromatic number, depending on the graph's degree and density
- A strengthening of Brooks' theorem
- Coloring the hypergraph of maximal cliques of a graph with no long path
- Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs
- Constructions of \(k\)-critical \(P_5\)-free graphs
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Note on the colouring of graphs
- Linearly χ‐bounding (P6, C4)‐free graphs*
- Coloring Claw-Free Graphs with $\Delta-1$ Colors
- Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
This page was built for publication: Strengthening Brooks' chromatic bound on \(P_6\)-free graphs