Weakening total coloring conjecture and Hadwiger's conjecture on total graphs

DOI10.37236/11032MaRDI QIDQ6117407zbMATH OpenWikidataFDO

Authors Manu Basavaraju, L. Sunil Chandran, Mathew C. Francis, Ankur Naskar

Publication date 19 February 2024

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Hadwiger's conjecture is one of the most important and long-standing conjectures in graph theory. Reed and Seymour showed in 2004 that Hadwiger's conjecture is true for line graphs. We investigate this conjecture on the closely related class of total graphs. The total graph of $G$, denoted by $T(G)$, is defined on the vertex set $V(G)sqcupE(G)$ with $c_1,c_{2}inV(G)sqcupE(G)$ adjacent whenever $c_1$ and $c_2$ are adjacent to or incident on 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 true for $T(G)$. The total chromatic number $$ of a graph $G$ is defined to be equal to the chromatic number of its total graph. That is, $$. Another well-known conjecture in graph theory, the total coloring conjecture or TCC, states that for every graph $G$, $$, where $Delta(G)$ is the maximum degree of $G$. We show that if a weaker version of the total coloring conjecture (weak TCC) namely, $$, is true for a class of graphs $mathcalF$ that is closed under the operation of taking subgraphs, then Hadwiger's conjecture is true for the class of total graphs of graphs in $mathcalF$. This motivated us to look for classes of graphs that satisfy weak TCC. It may be noted that a complete proof of TCC for even 4-colorable graphs (in fact even for planar graphs) has remained elusive even after decades of effort; but weak TCC can be proved easily for 4-colorable graphs. We noticed that in spite of the interest in studying $$ in terms of $chi(G)$ right from the initial days, weak TCC is not proven to be true for $k$-colorable graphs even for $k=5$. In the second half of the paper, we make a contribution to the literature on total coloring by proving that $$ for every 5-colorable graph $G$.

Recommendations

• The total chromatic number of graphs having large maximum degree
• Recent results on the total chromatic number
• scientific article; zbMATH DE number 98760
• The total chromatic number of split-indifference graphs
• Total coloring conjecture for certain classes of graphs

Cites work

• scientific article; zbMATH DE number 3659620 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• A bound on the total chromatic number
• A survey of -boundedness
• An upper bound for the total chromatic number
• Determining the total colouring number is NP-hard
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Graph theory
• Hadwiger's conjecture for 3-arc graphs
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Hadwiger's conjecture for line graphs
• Hadwiger's conjecture for powers of cycles and their complements
• Hadwiger's conjecture for proper circular arc graphs
• Hadwiger's conjecture for quasi-line graphs
• Hadwiger's conjecture for squares of 2-trees
• Hadwiger's conjecture for the complements of Kneser graphs
• List-colourings of graphs
• On Total Chromatic Number of a Graph
• On the total coloring of certain graphs
• On the total coloring of planar graphs.
• On total 9-coloring planar graphs of maximum degree seven
• Planar graphs of maximum degree seven are Class I
• SOME UNSOLVED PROBLEMS IN GRAPH THEORY
• The Colour Numbers of Complete Graphs
• The total chromatic number of any multigraph with maximum degree five is at most seven
• The total coloring of a multigraph with maximal degree 4
• Total colourings of graphs
• Über eine Eigenschaft der ebenen Komplexe

This page was built for publication: Weakening total coloring conjecture and Hadwiger's conjecture on total graphs

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