Ottawa–Carleton
Discrete Mathematics Group

21 November 2008, 11.30am
HP4351, Carleton

Let G be a plane graph with maximum face size Δ^*. If all faces of G with size four or more are vertex disjoint, then G has a cyclic coloring with Δ^* + 1 colors, i.e., a coloring such that all vertices incident with the same face receive distinct colors.

We discuss the background behind this statement, in particular three related conjectures: Ringel's conjecture, Ore and Plummer conjecture, and Albertson's conjecture. Then we present known results about cyclic colorings and finally we highlight the discharging method that we used to prove our result that answers Albertson's conjecture in more general settings.

This is joined work with Jernej Azarija, Rok Erman, Daniel Kral, and Matjaz Krnc.