Abstract: Colorings of graphs form a prominent topic in graph theory. Several relaxations of ordinary colorings have been introduced and intensively studied. In this talk, we focus on circular colorings of line graphs. A proper circular k-edge-coloring, for a real k >= 1, is a coloring by real numbers from the interval [0,k) such that the difference modulo k of the colors c1 and c2 assigned to incident edges is at least 1; that is, 1 >= |c1-c2| >= k-1.
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; that is, 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 a graph contains a clique of order D.
Our research is motivated by a conjecture of Jaeger and Swart 1979 (which turned out to be false) that high girth cubic graphs have chromatic index 3. Our results imply that the relaxation of the conjecture to circular colorings is true: the circular chromatic index of high girth cubic graphs is close to 3. Among the ingredients of our proof are recent results on systems of independent representatives and hypergraph matchability by Aharoni, Haxell, Meshulam, and others, which we also briefly survey during the talk. This work is joint with Tomas Kaiser, Riste Skrekovski, and Xuding Zhu.