View all Seminars  |  Download ICal for this event

Hadwigers conjecture and total coloring

Series: M.Tech (Research) Colloquium- ONLINE

Speaker: Mr. Ankur NaskarM.Tech (Research) studentDept. of CSA

Date/Time: Jul 28 16:00:00

Location: Microsoft Teams - ONLINE

Faculty Advisor: Prof. Sunil L Chandran

Hadwigers conjecture is one of the most important and long-standing conjectures in graph theory. It was established that proving Hadwigers conjecture is equivalent to proving the conjecture for the special class of graphs that can be expressed as the square of some other graph. However, it is difficult to prove Hadwigers conjecture even for the squares of highly specialised graph classes. We decided to investigate the squares of subdivided graphs (a subdivided graph is a graph that can be obtained from another graph $H$ by replacing each edge $uv$ of $H$ by a path $uwv$, where $w$ is a new vertex).
It turns out that squares of subdivided graphs are exactly the class of total graphs, well-studied in the context of the total coloring conjecture, another well-known and long-standing conjecture in graph theory. 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}in V(G)sqcup E(G)$ adjacent whenever $c_{1}$ and $c_{2}$ are adjacent to or incident on each other in $G$. The total-chromatic number $chi(G)$ of a graph $G$ is defined to be equal to the chromatic number of its total graph. That is, $chi(G)=chi(T(G))$.
The total coloring conjecture or textit{TCC} states that for every graph $G$, $chi(G)leqDelta(G)+2$. Though Hadwigers conjecture was proved for the closely related class of line graphs 20 years ago itself, Hadwigers conjecture is not yet studied in the context of total graphs. In this thesis, the following results are proved: (i) There exists a constant $C$ such that, if the connectivity of $Ggeq C$, then Hadwigers conjecture is true for $T(G)$.
(ii) Let $mathcal{F}$ be a class of graphs that is closed under the operation of taking subgraphs. If a weaker version of the total coloring conjecture (weak textit{TCC}) namely, $chi(G)leqDelta(G)+3$, is true for the class $mathcal{F}$, then Hadwigers conjecture is true for the class ${T(G): Gin mathcal{F} }$. The second statement motivates one to look for classes of graphs that satisfy weak textit{TCC}. It may be noted that a complete proof of textit{TCC} for even $4$-colorable graphs (in fact even for planar graphs) has remained elusive even after decades of effort; but weak textit{TCC} can be proved easily for $4$-colorable graphs.
It was noticed that in spite of interest in studying $chi(G)$ in terms of $chi(G)$ right from the initial days, weak textit{TCC} is not proven to be true for $k$-colorable graphs even for $k=5$.
In the latter half of the thesis, an important contribution to the total coloring literature is made by proving that $chi(G)leq Delta(G)+3$, for every $5$-colorable graph $G$. Being close to some of the well studied topics in total coloring, it seems that this is a long-pending addition to the literature.
Microsoft teams link:

Speaker Bio:

Host Faculty: