The circular chromatic index of graphs of high girth

Thursday, February 7, 2008 -
2:15pm to 4:15pm
Colorings of graphs form a prominent topic in graph theory. Several relaxations of usual colorings have been introduced and intensively studied. In this talk, we focus on circular colorings. A proper circular k-coloring, for a real $k\ge 1$, is a coloring by real numbers from the interval $[0,k)$ such that the difference modulo $k$ of the colors $c_1$ and $c_2$ assigned to adjacent vertices is at least one, i.e., $1\le |c_1-c_2|\le k-1$. It is easy to observe that the chromatic number of a graph is always the ceiling of its circular chromatic number.A classical theorem of Vizing states that the edges of every graph $G$ with maximum degree $D$ can be colored by at most $D+1$ colors so that no two incident edges have the same color, i.e., the chromatic index of $G$ is at most $D+1$. We show that for every $e>0$ there exists $g$ such that the circular chromatic index of a graph $G$ with maximum degree $D$ whose girth is at least $g$ does not exceed $D+e$. Note that the index must be at least $D$ because the line graph of such graph $G$ contains a clique of order $D$.Our research is motivated by a conjecture of Jaeger and Swart 1979 (that turned out to be false) that high girth cubic graphs have chromatic index three. Our results imply that the conjecture is true when relaxed to circular colorings: the circular chromatic index of high girth cubic graphs is close to three.One of the ingredients of our proof are results on systems of independent representatives and hypergraph matchability of by Aharoni, Haxell, Meshulam and others, which we also briefly survey during the talk. Based on joint work with Tomas Kaiser, Riste Skrekovski and Xuding Zhu.
Speaker: 
Daniel Král'
Charles University, Prague
Event Location: 
Fine Hall 314