max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Hadwiger's Conjecture and Squares of Chordal Graphs Davis Issac Max-Planck-Institut für Informatik - D1 AG1 Mittagsseminar (own work) D1We use this to send out email in the morning. AG Audience English
Date: Thursday, 21 July 2016 13:00 30 Minutes Saarbrücken E1 4 024
 Hadwiger's conjecture states that for every graph $G$, $\chi(G)\le \eta(G)$, where $\chi(G)$ is the chromatic number and $\eta(G)$ is the size of the largest clique minor in $G$. In this work, we show that to prove Hadwiger's conjecture in general, it is sufficient to prove Hadwiger's conjecture for the class of graphs $\mathcal{F}$ defined as follows: $\mathcal{F}$ is the set of all graphs that can be expressed as the square graph of a split graph. Since split graphs are a subclass of chordal graphs, it is interesting to study Hadwiger's Conjecture in the square graphs of subclasses of chordal graphs. Here, we study a simple subclass of chordal graphs, namely $2$-trees and prove Hadwiger's Conjecture for the squares of the same.
Name(s): Davis Issac