# Hadwiger's Conjecture for Proper Circular Arc Graphs

Research paper by Naveen Belkale, L. Sunil Chandran

Indexed on: 07 Jul '06Published on: 07 Jul '06Published in: Mathematics - Combinatorics

#### 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 of \$k\$ vertices is a minor of \$G\$. We prove Hadwiger's conjecture for proper circular arc graphs.