Borodin-Kostochka conjecture holds for odd-hole-free graphs

DOI10.1007/S00373-024-02753-0MaRDI QIDQ6154380OpenAlexFDO

Authors Rong Chen, Kaiyang Lan, Xinheng Lin, Yidong Zhou

Publication date 15 February 2024

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberodd-hole-free graphsBorodin-Kostochka conjecture

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Recommendations

• Borodin-Kostochka conjecture holds for \(\overline{K_{1 , 3}} \)-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
• Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors
• Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs

Cites work

• A strengthening of Brooks' theorem
• A survey of \(\chi\)-boundedness
• 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 Claw-Free Graphs with $\Delta-1$ Colors
• Coloring hammer-free graphs with \(\Delta - 1\) colors
• Graph colouring and the probabilistic method
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Note on the colouring of graphs
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density

Cited in

(4)

• Coloring hammer-free graphs with \(\Delta - 1\) colors
• Borodin-Kostochka conjecture holds for \(\overline{K_{1 , 3}} \)-free graphs
• Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors
• Borodin-Kostochka's conjecture on \(\{P_2 \cup P_3, C_4\}\)-free graphs

This page was built for publication: Borodin-Kostochka conjecture holds for odd-hole-free graphs

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