AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

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.

Davis Issac

--email hidden

passcode not visible

logged in users only