English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Borodin and Kostochka conjectured that every graph $G$ with maximum degree$\Delta \ge 9$ satisfies $\chi \le \max\{\omega, \Delta-1\}$. We carry out anin-depth study of minimum counterexamples to the Borodin-Kostochka conjecture.Our main tool is the identification of graph joins that are $f$-choosable,where $f(v) = d(v) - 1$ for each vertex $v$. Since such a join cannot be aninduced subgraph of a vertex critical graph with $\chi = \Delta$, we have awealth of structural information about minimum counterexamples to theBorodin-Kostochka conjecture.  Our main result proves that certain conjectures that are prima facie weakerthan the Borodin-Kostochka conjecture are in fact equivalent to it. One suchequivalent conjecture is the following: Any graph with $\chi \ge \Delta = 9$contains $K_3 * \bar{K_6}$ as a subgraph.

Coloring a graph with $\Delta-1$ colors: Conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker