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

Hadwiger's conjecture is one of the most important and long-standingconjectures in graph theory. Reed and Seymour showed in 2004 that Hadwiger'sconjecture is true for line graphs. We investigate this conjecture on theclosely related class of total graphs. The total graph of $G$, denoted by$T(G)$, is defined on the vertex set $V(G)\sqcup E(G)$ with $c_1,c_2\inV(G)\sqcup E(G)$ adjacent whenever $c_1$ and $c_2$ are adjacent to or incidenton each other in $G$. We first show that there exists a constant $C$ such that,if the connectivity of $G$ is at least $C$, then Hadwiger's conjecture is truefor $T(G)$. The total chromatic number $\chi"(G)$ of a graph $G$ is defined tobe equal to the chromatic number of its total graph. That is,$\chi"(G)=\chi(T(G))$. Another well-known conjecture in graph theory, the totalcoloring conjecture or TCC, states that for every graph $G$,$\chi"(G)\leq\Delta(G)+2$, where $\Delta(G)$ is the maximum degree of $G$. Weshow that if a weaker version of the total coloring conjecture (weak TCC)namely, $\chi"(G)\leq\Delta(G)+3$, is true for a class of graphs $\mathcal{F}$that is closed under the operation of taking subgraphs, then Hadwiger'sconjecture is true for the class of total graphs of graphs in $\mathcal{F}$.This motivated us to look for classes of graphs that satisfy weak TCC. It maybe noted that a complete proof of TCC for even 4-colorable graphs (in fact evenfor planar graphs) has remained elusive even after decades of effort; but weakTCC can be proved easily for 4-colorable graphs. We noticed that in spite ofthe interest in studying $\chi"(G)$ in terms of $\chi(G)$ right from theinitial days, weak TCC is not proven to be true for $k$-colorable graphs evenfor $k=5$. In the second half of the paper, we make a contribution to theliterature on total coloring by proving that $\chi"(G)\leq\Delta(G)+3$ forevery 5-colorable graph $G$.

Weakening Total Coloring Conjecture: Weak TCC and Hadwiger's Conjecture on Total Graphs