Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

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)
What and Who
Title:Hadwiger's Conjecture and Squares of Chordal Graphs
Speaker:Davis Issac
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Thursday, 21 July 2016
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
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.
Contact
Name(s):Davis Issac
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
Created by:Davis Issac, 06/26/2016 12:19 PMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Davis Issac, 06/26/2016 12:21 PM
  • Davis Issac, 06/26/2016 12:19 PM -- Created document.