Schedule for: 16w5120 - New Trends in Graph Coloring

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

In order to solve a problem in list coloring, Dvorak and Postle introduced the more general notion of DP-coloring (they called it "correspondence coloring"). This new notion seems very promising. The goal of the talk is to present the language of DP-coloring and some of its interesting properties. In particular, we will discuss DP coloring of multigraphs and ask some questions.

Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

We show that planar triangle-free graphs have exponential number of 3-colorings if and only if the following conjecture holds: There exists $\varepsilon>0$ such that if $G$ is a planar graph and $X$ is a set its edges such that $G-X$ is triangle-free, then for some $Y\subseteq X$ of size at least $\varepsilon|X|$, the graph $G-(X\setminus Y)$ is 3-colorable. We also show some special cases where the latter conjecture holds. Based on joint work with J.-S. Sereni.

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Thue (1906) constructed an arbitrarily long string of three characters containing no substring of even length where the first half of the substring is the same as the second half. We can think of Thue's theorem as a result about 3-colouring paths, which naturally suggests a generalisation for arbitrary graphs. A nonrepetitive colouring of a graph $G$ is a function that assigns each vertex of $G$ a colour, such that for every path $P$ of even length in $G$, the sequence of colours on the first half of $P$ is distinct from the sequence of colours on the second half of $P$. The nonrepetitive chromatic number of $G$ is the minimum number of colours in a nonrepetitive colouring of $G$. It follows from Thue's result that the nonrepetitive chromatic number of a path (of length at least 4) equals 3. What about nonrepetitive colouring of other graph classes? Alon, Grytczuk, Haluszczak and Riordan (2002) proved that bounded degree graphs have bounded nonrepetitive chromatic number; in particular, graphs with maximum degree $\Delta$ are nonrepetitively $O(\Delta^2)$-colourable. The proof is an elegant example of the Lovász Local Lemma. Using a recent technique called `entropy compression', Dujmovic, Joret, Kozik and Wood (2015) reduced this bound to $(1+o(1))\Delta^2$. Non-repetitive colourings have been studied for several well-structured graph families. For example, Brešar, Grytczuk, Klavžar, Niwczyk and Peterin (2007) proved that every tree is nonrepetitively 4-colourable. Kündgen and Pelsmajer (2008) generalised this result for graphs of bounded treewidth. Nešetřil, Ossona de Mendez and Wood (2011) studied nonrepetitive colourings of subdivisions, and concluded that graph classes with bounded nonrepetitive chromatic number have bounded expansion. A challenging open problem, due to Grytczuk (2007), is whether planar graphs have bounded nonrepetitive chromatic number. The best known upper bound for $n$-vertex planar graphs is $O(\log n)$ due to Dujmovic, Frati, Joret and Wood (2013). This bound was generalised by Dujmovic, Morin and Wood~(2013) for graphs excluding a fixed topological minor. The proof employs powerful tools such as the Robertson--Seymour graph minor structure theorem. This talk will survey these results, focusing on the tools used, which should be of wide interest.

In the multicoloring problem, also known as $(a:b)$ or$b$-fold coloring, we are given a graph $G$ and a set of a colors, and the task is to assign a subset of $b$ colors to each vertex of $G$ so that adjacent vertices receive disjoint color subsets. This natural generalization of the classic coloring problem (the $b=1$ case) is equivalent to finding a homomorphism to the Kneser graph with parameters $a$ and $b$. It is tightly connected with the fractional chromatic number, and has multiple applications within computer science. We study the complexity of determining whether a graph has an $(a:b)$-coloring. Nederlof showed in 2008 a $(b+1)^nn^{O(1)}$-time algorithm for $(a:b)$-coloring. Our main result is that this is essentially optimal: there is no algorithm with running time $2^{o(log b)n}$ unless the ETH fails. The crucial ingredient in our hardness reduction is the usage of detecting matrices of Lindström (1965), which is a combinatorial tool that, to the best of our knowledge, has not yet been used for proving complexity lower bounds. This is joint work with Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala and Marcin Wrochna (University of Warsaw)."

The entropy compression method is an algorithmic technique that was invented by Moser and Tardos in order to give an effective proof of the Lovász Local Lemma (the LLL for short). It turns out that avoiding the LLL and applying the entropy compression method directly can lead to improvements, sometimes significant, in combinatorial bounds. The Local Cut Lemma (the LCL for short) is a generalization of the LLL that implies these new combinatorial results. It hides technical parts of the method and thus makes the arguments simpler and shorter. Although the LCL was inspired by the entropy compression method, it has a direct probabilistic proof (similar to the classical proof of the LLL); in particular, it not only shows that a certain probability is positive, but also gives an explicit lower bound for that probability. In this talk, we will discuss the LCL and some of its applications, as well as its connections with the entropy compression.

Hadwiger (infamously) conjectured that there is a tight relationship between the chromatic number of a graph and the maximum size of a clique minor - specifically, every graph with chromatic number at least $t$ contains $K_t$ as a minor. Lescure and Meynial and later Abu-Khzam and Langston independently extended Hadwiger's to graph immersions, an alternate model of graph containment. Specifically, they conjecture that every graph with chromatic number $t$ contains $K_t$ as an immersion. We present new bounds on the relationship between the chromatic number and the maximal size of a clique immersion in a graph. For general graphs, building on the recent work of Dvorak and Yepremyn, we show that every graph with $\chi(G) \ge 3.54t$ contains $K_t$ as an immersion. A particularly interesting case of Hadwiger's conjecture is when restricted to graphs of small independence number. We show that every graph on $n$ vertices with independence number $\alpha = 2$ contains a $K_t$ immersion with $t = .4 n$. We conclude with several open questions. This is joint work with Tien-Nam Le and Gregory Gauthier.

Coloring graphs in such a way that each subgraph induced by a color class has bounded maximum degree receives extensive attention recently. Motivated by Grotzsch's theorem, Steinberg's conjecture and other related results, we consider coloring planar graphs with some cycles forbidden. In this talk, we characterize all minimal sets S in which every planar graph G with no cycle lengths belonging to S has each of the following properties: (1) V(G) can be partitioned into a stable set and a set that induces a graph of bounded maximum degree, (2) V(G) can be partitioned into two sets each induces a graph of bounded maximum degree, and (3) V(G) can be partitioned into two stable sets and one set that induces a graph of bounded maximum degree. This is joint with Ilkyoo Choi and Sang-il Oum.

We investigate intersection graphs of pseudo-disks (a pseudo-disk is the homeomorphic image of a disk in the plane) whose interiors are pairwise disjoint (i.e. which may only intersect at their boundaries), and in particular we answer a question of Reed and Shepherd (1996) and a question of Hlineny (1998) on their chromatic number. We also consider the chromatic number of intersection graphs of pairwise non-crossing Jordan curves in the plane. There is a nice application to the problem of bounding the integrality gap for the maximum (vertex-)packing of cycles in planar digraphs.

We prove that every 3-edge-connected graph has a 3-flow that takes on a zero value on at most one sixth of the edges. The graph $K_4$ demonstrates that this $\frac{1}{6}$ ratio is best possible; there is an infinite family where $\frac 16$ is tight. The proof involves interesting work with connectivity of the graph (relaxing to subdivisions of 2-edge-connected graphs and then reducing to cyclically 4-edge-connected ones). Joint work with M. DeVos, J. McDonald, I. Pivotto, and E. Rollova.

Problems concerning coloring graphs embedded in the plane have always been among the most intensively studied problems in graph theory. In the talk, we will present some recent results, which have been obtained with various groups of collaborators, on three classical problems in the area: Steinberg's Conjecture from 1976, the Cyclic Coloring Conjecture of Borodin from 1984, and the Cyclic Coloring Conjecture of Plummer and Toft from 1987.

We show that linegraphs of multigraphs have chromatic number at most $\max(\omega, \lceil(5\Delta+3)/6\rceil)$. The result is sharp, as shown by line graphs of blow-ups of the 5-cycle. For comparison this bound is stronger than Reed's conjecture when $\omega > 2\Delta/3$. The proof uses Tashkinov trees. Based on joint work with Landon Rabern.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.