Coloring (P5,gem) ({P}_{5},\text{gem})‐free graphs with Δ−1 {\rm{\Delta }}-1 colors

DOI10.1002/JGT.22845MaRDI QIDQ6046645zbMATH OpenFDO

Authors Daniel W. Cranston, Landon Rabern

Publication date 5 October 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

graph coloringBrooks' theorem\(P_5\)-freeBorodin-Kostochka conjecturegem-free

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: The Borodin-Kostochka Conjecture states that for a graph $G$, if $Delta(G)geq9$ and $omega(G)leqDelta(G)-1$, then $chi(G)leqDelta(G)-1$. We prove the Borodin-Kostochka Conjecture for $(P_5,extgem)$-free graphs, i.e., graphs with no induced $P_5$ and no induced $K_{1}vee{P}_4$.

Recommendations

• Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs
• Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
• Coloring (gem, co‐gem)‐free graphs
• The chromatic number of \(\{P_5,K_4\}\)-free graphs
• A bound for the chromatic number of \((P_5, \text{gem})\)-free graphs

Cites work

• scientific article; zbMATH DE number 3719178 (Why is no real title available?)
• scientific article; zbMATH DE number 1286500 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• A strengthening of Brooks' theorem
• Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs
• Coloring (gem, co‐gem)‐free graphs
• Coloring Claw-Free Graphs with $\Delta-1$ Colors
• Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
• Coloring graphs with no induced five‐vertex path or gem
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• The strong perfect graph theorem

Cited in

(16)

• A conjecture of Borodin and a coloring of Grünbaum
• Coloring hammer-free graphs with \(\Delta - 1\) colors
• Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
• The maximum size of an edge 2-neighborhood in \(P_5\)-free graphs
• Partitioning of a graph into induced subgraphs not containing prescribed cliques
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• On the structure of (\(P_{5}\),\,gem)-free graphs
• Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs
• 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
• Strengthening Brooks' chromatic bound on \(P_6\)-free graphs
• Borodin-Kostochka's conjecture on \(\{P_2 \cup P_3, C_4\}\)-free graphs
• A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
• A Conjecture of Borodin and a Coloring of Grünbaum
• Borodin-Kostochka conjecture holds for odd-hole-free graphs
• Coloring (gem, co‐gem)‐free graphs

This page was built for publication: Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors

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