CanaDAM 2019
SFU Harbour Centre, May 29 - 31, 2019

Graph coloring I
Chair: Bernard Lidický (Iowa State University)

JAMIE DE JONG, University of Waterloo
Jaeger’s Strong 3-Flow Conjecture for Graphs in Low Genus Surfaces  [PDF]

In 1972, Tutte proposed the 3-Flow Conjecture; that all 4-edge-connected graphs have a nowhere zero 3-flow. This was extended by Jaeger (1979) to allow vertices to have a non-zero difference (modulo 3) between the inflow and outflow. Richter et al. (2016) proved Jaeger’s Conjecture for planar graphs. Here we consider the background for these problems, as well as how to prove Jaeger's Conjecture for projective planar graphs, and discuss extending this to the torus.

STANISŁAW RADZISZOWSKI, Rochester Institute of Technology
On a Diagonal Conjecture for Classical Ramsey Numbers  [PDF]

Let $R(a_1, \cdots, a_r)$ denote the classical $r$-color Ramsey number for integers $a_i \ge 2$. The Diagonal Conjecture (DC) for classical Ramsey numbers poses that if $a_1, \cdots, a_r$ are integers no smaller than 3 and $a_{r-1} \leq a_r$, then $R(a_1, \cdots, a_{r-2}, a_{r-1}-1, a_r +1) \leq R(a_1, \cdots, a_r)$. We obtain some implications of this conjecture, present evidence for its validity, and discuss related problems.

Let $R_r(k)$ stand for the $r$-color Ramsey number $R(k, \cdots, k)$. It is known that $\lim_{r \rightarrow \infty} R_r(3)^{1/r}$ exists, either finite or infinite, the latter conjectured by Erd\H{o}s. This limit is related to the Shannon capacity of $K_3$-free graphs. We prove that if DC holds, and $\lim_{r \rightarrow \infty} R_r(3)^{1/r}$ is finite, then $\lim_{r \rightarrow \infty} R_r(k)^{1/r}$ is finite for every integer $k \geq 3$.

This is joint work with Meilian Liang and Xiaodong Xu

INGO SCHIERMEYER, Technische Universität Bergakademie Freiberg
Polynomial chi-binding functions and forbidden induced subgraphs - a survey  [PDF]

A graph $G$ with clique number $\omega(G)$ and chromatic number $\chi(G)$ is {\it perfect} if $\chi(H)=\omega(H)$ for every induced subgraph $H$ of $G.$ A family $\cal{G}$ of graphs is called $\chi$-bounded with binding function $f$ if $\chi(G') \leq f(\omega(G'))$ holds whenever $G \in \cal{G}$ and $G'$ is an induced subgraph of $G.$

In this talk we will present a survey on polynomial $\chi $-binding functions. Especially we will address perfect graphs, hereditary graphs satisfying the Vizing bound ($\chi \leq \omega +1$), graphs having linear $\chi $-binding functions and graphs having non-linear polynomial $\chi $-binding functions. Thereby we also survey polynomial $\chi $-binding functions for several graph classes defined in terms of forbidden induced subgraphs, among them $2K_2$-free graphs, $P_k$-free graphs, $claw$-free graphs, and $diamond$-free graphs.

THOMAS SCHWESER, Technische Universität Ilmenau
On DP-Coloring of Digraphs  [PDF]

DP-coloring is a relatively new coloring concept by Dvo\v{r}\'ak and Postle and was introduced as an extension of list-colorings of (undirected) graphs. It transforms the problem of finding a list-coloring of a given graph $G$ with a list-assignment $L$ to finding an independent transversal in an auxiliary graph with vertex set $\{(v,c) ~|~ v \in V(G), c \in L(v)\}$. In this talk, we extend the definition of DP-colorings to digraphs using the approach from Neumann-Lara where a coloring of a digraph is a coloring of the vertices such that the digraph does not contain any monochromatic directed cycle. Furthermore, we present a Brooks' type theorem regarding the DP-chromatic number, which extends various results on the (list-)chromatic number of digraphs.

This is joint work with J\o rgen Bang-Jensen and Thomas Bellitto (University of Southern Denmark) and Michael Stiebitz (Technische Universität Ilmenau).

RINOVIA SIMANJUNTAK, Institut Teknologi Bandung, Indonesia
On $D-$Magic Hypercubes  [PDF]

For a set of distances $D$, a graph $G$ of order $n$ is said to be $D-$magic if there exists a bijection $f:V\rightarrow \{1,2, \ldots, n\}$ and a constant $k$ such that for any vertex $x$, $\sum_{y\in N_D(x)} f(y) ={\sf k}$, where $N_D(x)=\{y|d(y,x)=j, j\in D\}$.

In this talk, we search for all sets of distances $D$s such that the hypercube is $D-$magic. We utilise well-known properties of (bipartite) distance-regular graphs to construct the $D-$magic labelings for hypercubes.