CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Edge-Colouring and Structures on Line Graphs
Org: Jessica McDonald (Simon Fraser University)

LUIS GODDYN, Simon Fraser University
Edge List Colouring of Planar Cubic Graphs  [PDF]

Let $G$ be a planar cubic multigraph having $b(G)$ cut-edges. Then $G$ is $4$-edge list colourable. Indeed, only a few edges of $G$ require lists of length $4$. We show, nonconstructively, that there exists $F \subseteq E(G)$ with $|F| \le 3b(G)$ such that $G$ has a proper $L$-edge colouring for every list assignment $L$ satisfying $|L(e)| \ge 3$ ($e \in E(G)$) and $|L(e)| \ge 4$ ($e \in F$). This is joint work with Andrea Spencer.

ANDREW KING, Columbia University
Bounding the chromatic index: Exploiting and sidestepping structure  [PDF]

One can prove Reed's omega, Delta, chi conjecture for line graphs by exploiting structure in a straightforward way. For a local strengthening of the conjecture, a very different approach is needed. In this talk I will discuss these two proofs as well as theorems that, at least for the original conjecture, let us sidestep the structure of line graphs altogether.

Joint work with Maria Chudnovsky, Matthieu Plumettaz, and Paul Seymour.

OGUZ KURT, The Ohio State University
The rule trees and the cubic root bound on the chromatic index  [PDF]

The famous Goldberg-Seymour Conjecture states that the linearity gap between the chromatic index $\chi'$ and the fractional chromatic index $\chi'^*$ is less than 1 if $\chi' >\Delta+ 1$. Here, we show that this statement holds if $\chi' > \Delta+ \sqrt[3]{\Delta/2} $. While the starting point of our proof is Tashkinov trees and VKT-trees by Chen et. al., we will use a more general tree definition called the rule trees in our proof.

JESSICA MCDONALD, Simon Fraser University
Kempe equivalence of edge colourings in (sub)cubic graphs  [PDF]

Given a graph $G$ and two edge-colourings $\phi$ and $\psi$ of $G$, we say that $\phi$ and $\psi$ are Kempe equivalent if one can be obtained from the other via a sequence of Kempe changes, i.e., switches of pairs of colours along maximal alternating paths or cycles. In this talk we show that all $4$-edge-colourings of a (sub)cubic graph are Kempe equivalent.

Joint work with Bojan Mohar and Diego Scheide.

DIEGO SCHEIDE, Simon Fraser University
Acyclic list edge-colourings of degenerate graphs  [PDF]

The talk will give a very simple and efficient algorithm to produce an acyclic (proper, no bichromatic cycles) edge-colouring of a graph. As a result, any $d$-degenerate graph $G$ is $k$-edge-choosable, where $k=\Delta(G)+(d-1)(2d-1)$. For a planar graph $G$, the algorithm can be improved to show that $G$ is $(\Delta+20)$-edge-choosable.

Joint work with Bojan Mohar and Gasper Fijavz.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria