Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654364 | European Journal of Combinatorics | 2009 | 11 Pages |
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 G has chromatic number k, then a complete graph with k vertices is a minor of G. We prove Hadwiger's conjecture for proper circular arc graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Naveen Belkale, L. Sunil Chandran,