Hadwiger's Conjecture for Proper Circular Arc Graphs
arXiv:math/0605503
Abstract
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 graphs which have a circular arc representation where no arc is completely contained in any other arc. Hadwiger's conjecture states that if a graph has chromatic number , then a complete graph of vertices is a minor of . We prove Hadwiger's conjecture for proper circular arc graphs.
18 pages, 2 figures