Seminars

View all Seminars  |  Download ICal for this event

Hadwigers conjecture and total coloring.

Series: M.Tech (Research)Thesis Defence -ONLINE

Speaker: Mr. Ankur NaskarM.Tech (Research) student,Dept. of CSA

Date/Time: Dec 13 11:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor: Prof. Sunil L Chandran

Abstract:
Hadwigers conjecture is one of the most important and long-standing conjectures in graph theory. It was established recently 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 byT(G), is defined on the vertex set V(G) ⊔ E(G), with c1,c2 ∈ V(G) ⊔ E(G) adjacent whenever c1 and c2 are adjacent to or incident on each other in G. The total-chromatic number χ′′(G) of a graph G is defined to be equal to the chromatic number of its total graph. That is, χ′′(G) = χ(T(G)). The total coloring conjecture or TCC states that for every graph G, χ′′(G) ≤ ∆(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 G ≥ C, then Hadwigers conjecture is true for T(G).
(ii) Let 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 TCC) namely, χ′′(G) ≤ ∆(G) + 3, is true for the class F, then Hadwigers conjecture is true for the class {T(G) : G ∈ F}.
The second statement motivates one 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. It was noticed that in spite of interest in studying χ′′(G) in terms of χ(G) right from the initial days, weak 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 χ′′(G) ≤ ∆(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:
https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZWEyMmNiMWUtNzY1ZS00ZmY3LTkyYmUtNGVjOTNkNGU0NWQx%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22ed2e5ccd-b870-455c-862e-26e9ab1908be%22%7d

Speaker Bio:

Host Faculty: