Conjectures equivalent to the Borodin-Kostochka Conjecture that are a priori weaker

Details Conjectures equivalent to the Borodin-Kostochka Conjecture that are a priori weaker Conjectures equivalent to the Borodin-Kostochka Conjecture that are a priori weaker

2012-03-24

arxiv.org/abs/1203.5380v1

Mathematics

Combinatorics

Scientific paper

Borodin and Kostochka conjectured that every graph $G$ with maximum degree $\Delta \geq 9$ satisfies $\chi \leq \max\{\omega, \Delta-1\}$. We carry out an in-depth study of minimum counterexamples to the Borodin-Kostochka conjecture. Our main tool is the classification of graph joins $A * B$ with $|A| \geq 2$, $|B| \geq 2$ which are $f$-choosable, where $f(v) = d(v) - 1$ for each vertex $v$. Since such a join cannot be an induced subgraph of a vertex critical graph with $\chi = \Delta$, we have a wealth of structural information about minimum counterexamples to the Borodin-Kostochka Conjecture. Our main result is to prove that certain conjectures that are a priori weaker than the Borodin-Kostochka Conjecture are in fact equivalent to it. One such equivalent conjecture is the following: Any graph with $\chi \geq \Delta = 9$ contains $K_3 * E_6$ as a subgraph.

Affiliated with

Also associated with

No associations

Rating

Conjectures equivalent to the Borodin-Kostochka Conjecture that are a priori weaker does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Conjectures equivalent to the Borodin-Kostochka Conjecture that are a priori weaker, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conjectures equivalent to the Borodin-Kostochka Conjecture that are a priori weaker will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-38914