CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Graph Colouring and Games
Org: Evan DeCorte (McGill)

EVAN DECORTE, McGill University
The hyperbolic Hadwiger-Nelson problem  [PDF]

Consider the graph $H(d)$ whose vertex set is the hyperbolic plane, and where two points are joined with an edge when their distance is equal to $d$. Asking for the chromatic number of this graph is the hyperbolic analogue to the famous Hadwiger-Nelson problem. One has the lower bound of $4$ for all $d>0$, as in the Euclidean case. Using spectral methods, we prove that with the additional requirement that the colour classes be measurable, one needs at least $6$ colours to properly colour $H(d)$ when $d$ is sufficiently large. This is joint work with Konstantin Golubev.

RINGI KIM, University of Waterloo
Coloring digraphs containing no cycles with two blocks.  [PDF]

A cycle with two blocks, $c(k,\ell)$, is an oriented cycle which consists of two internally (vertex) disjoint directed paths of lengths at least $k$ and $\ell$, respectively, from a vertex to another one. In 2007, Addario-Berry, Havet and Thomass\'e asked if, given positive integers $k$ and $\ell$ such that $k+\ell\ge 4$, any strongly connected digraph $D$ containing no $c(k,\ell)$ has chromatic number at most $k+\ell-1$.

We show that such digraph $D$ has chromatic number at most $O((k+\ell)^2)$, improving the previous upper bound $O((k+\ell)^4)$ of Cohen, Havet, Lochet and Nisse. This is joint work with Seog-Jin Kim, Jie Ma and Boram Park.

ROBERT ŠÁMAL, Charles University
Approximating the Petersen coloring conjecture  [PDF]

Petersen coloring (defined by Jaeger) is a mapping from the edges of a cubic graph to the edges of the Petersen graph, so that three edges incident to a single vertex are mapped to three edges incident to a single vertex. Jaeger conjectured that every cubic bridgeless graph admits a Petersen coloring.

This conjecture, if true, implies the cycle double cover conjecture and the Berge-Fulkerson conjecture.

We develop Jaeger's alternate formulation of Petersen coloring in terms of so-called normal 5-edge-colorings. In this formulation we provide partial results supporting the conjecture.

DOUGLAS B WEST, Zhejiang Normal University and University of Illinois
Online Sum Paintability: The Slow-Coloring Game  [PDF]

The "slow-coloring game" is played by Lister and Painter on a graph $G$. On each round, Lister marks a nonempty subset $M$ of the remaining vertices, scoring $|M|$ points. Painter colors a subset of $M$ that is independent in $G$. The game ends when all vertices are colored. Painter seeks to minimize the total score; Lister seeks to maximize it. The score under optimal play is the "slow-color cost" of $G$, written $s(G)$.

Trivial lower and upper bounds on $s(G)$ are the chromatic sum and the sum-paintability, which are sharp. We give sharp upper and lower bounds on $s(G)$ in terms of the independence number. We have a linear-time algorithm to compute $s(G)$ exactly when $G$ is a tree; among $n$-vertex trees, it is minimized by the star and maximized by the path (where it equals $3n/2$), We give good bounds on $s(K_{r,s})$. (Joint with Thomas Mahoney and Gregory Puleo.)

WING HONG TONY WONG, Kutztown University of Pennsylvania
Graph coloring games and ``nimbers"  [PDF]

There are many variations of graph coloring games. In this project, we discuss a scenario where Alice and Barbara take turns to color the vertices of a given graph, with Alice starting first, so that no adjacent vertices share the same color. The first player who is unable to color a vertex loses the game. We consider the following two versions: 1. Alice uses color $A$ and Barbara uses color $B$; 2. both of them use a common color $C$. Under both versions, we examine various families of graphs and determine which player has a winning strategy. Examples of such families include paths, cycles, rectangular grids, triangular grids, and Cayley graphs, etc. We also prove some general assertions about all graphs. ``Nimbers", also known as Grundy numbers, are involved in some of these proofs.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology