Record Details

Hadwiger's Conjecture On Circular Arc Graphs

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Hadwiger's Conjecture On Circular Arc Graphs
 
Creator Belkale, Naveen
 
Subject Graph Theory
Hadwiger's Conjecture
Circular Arc Graphs
Good Path Set
Successor Function
Clique Minor
Graph Minors
Mathematics
 
Description Conjectured in 1943, Hadwiger’s conjecture is one of the most challenging open problems in graph theory. Hadwiger’s conjecture states that if the chromatic number of a graph G is k, then G has a clique minor of size at least k. In this thesis, we give motivation for attempting Hadwiger’s conjecture for circular arc graphs and also prove the conjecture for proper circular arc graphs. Circular arc graphs are graphs whose vertices can be represented as arcs on a circle such that any two vertices are adjacent if and only if their corresponding arcs intersect. Proper circular arc graphs are a subclass of circular arc graphs that have a circular arc representation where no arc is completely contained in any other arc. It is interesting to study Hadwiger’s conjecture for circular arc graphs as their clique minor cannot exceed beyond a constant factor of its chromatic number as We show in this thesis. Our main contribution is the proof of Hadwiger’s conjecture for proper circular arc graphs. Also, in this thesis we give an analysis and some basic results on Hadwiger’s conjecture for circular arc graphs in general.
 
Contributor Chandran, Sunil
 
Date 2009-04-30T04:45:38Z
2009-04-30T04:45:38Z
2009-04-30T04:45:38Z
2007-07
 
Type Thesis
 
Identifier http://etd.iisc.ernet.in/handle/2005/475
 
Language en_US
 
Relation G21484