BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20211213T120000Z
UID:73bd9996f2400cdb685c802e39c1e7f2-231
DTSTAMP:19700101T120011Z
DESCRIPTION:Hadwigers conjecture and total coloring.
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/231/hadwigers-conjecture-and-total-coloring/
SUMMARY: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 :
<br>
(i)  There  exists  a  constant C such  that,  if  the  connectivity  of G ≥ C,  then  Hadwigers conjecture is true for T(G).
<br>
(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}.
<br>
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.
<br>
Microsoft teams link:
<br>
<a href="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">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</a>
DTSTART:20211213T120000Z
END:VEVENT
END:VCALENDAR