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

DOI10.1002/JGT.22845zbMATH Open1522.05104arXiv2006.02015MaRDI QIDQ6046645FDOQ6046645

Authors: Daniel W. Cranston, Landon Rabern 

Publication date: 5 October 2023

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

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$.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

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

Cited In (16)

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