Schedule for: 16w5120 - New Trends in Graph Coloring

Arriving in Banff, Alberta on Sunday, October 16 and departing Friday October 21, 2016
Sunday, October 16
16:00 - 17:30 Check-in begins at 16:00 on Sunday and is open 24 hours (Front Desk - Professional Development Centre)
17:30 - 19:30 Dinner
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.
(Vistas Dining Room)
20:00 - 22:00 Informal gathering (Corbett Hall Lounge (CH 2110))
Monday, October 17
07:00 - 08:45 Breakfast
Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.
(Vistas Dining Room)
08:45 - 09:00 Introduction and Welcome by BIRS Station Manager (TCPL 201)
09:00 - 10:00 Introductions and open problems (TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:00 Alexander Kostochka: DP-coloring
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.
(TCPL 201)
11:00 - 11:30 Free discussion and research in groups (TCPL 201)
11:30 - 13:00 Lunch (Vistas Dining Room)
13:00 - 14:00 Guided Tour of The Banff Centre
Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.
(Corbett Hall Lounge (CH 2110))
14:00 - 14:20 Group Photo
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!
(TCPL Foyer)
14:30 - 15:00 Zdenek Dvorak: Towards exponentially many 3-colorings of triangle-free planar graphs
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.
(TCPL 201)
15:00 - 15:30 Coffee Break (TCPL Foyer)
15:30 - 17:00 Paul Seymour: Tutorial: $\chi$-boundedness part 1 (TCPL 201)
17:00 - 18:00 Research in groups (TCPL)
18:00 - 19:30 Dinner
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.
(Vistas Dining Room)
Tuesday, October 18
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 09:45 David Wood: Non-repetitive colorings
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.
(TCPL 201)
09:45 - 10:15 Marthe Bonamy: Tight lower bounds for the complexity of multicoloring
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)."
(TCPL 201)
10:15 - 10:45 Coffee Break (TCPL Foyer)
10:45 - 11:15 Anton Bernshteyn: The Local Cut Lemma
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.
(TCPL 201)
11:15 - 12:00 Research in groups (TCPL)
12:00 - 13:30 Lunch (Vistas Dining Room)
14:30 - 15:00 Progress reports (TCPL 201)
15:00 - 15:30 Coffee Break (TCPL Foyer)
15:30 - 17:00 Alex Scott: Tutorial: $\chi$-boundedness part 2 (TCPL 201)
17:00 - 18:00 Research in groups (TCPL)
18:00 - 19:30 Dinner (Vistas Dining Room)
Wednesday, October 19
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 09:30 Paul Wollan: Forcing clique immersions with large chromatic number
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.
(TCPL 201)
09:30 - 10:00 Chun-Hung Liu: Characterizations of minimal cycle obstruction sets for balanced and unbalanced partitionable planar graphs
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.
(TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:00 Louis Esperet: Coloring pseudo-disks and Jordan curves
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.
(TCPL 201)
11:00 - 11:30 Research in groups (TCPL)
11:30 - 13:00 Lunch (Vistas Dining Room)
13:00 - 17:30 Free Afternoon (Banff National Park)
17:30 - 19:30 Dinner (Vistas Dining Room)
Thursday, October 20
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 09:30 Robert Samal: 3-Flows with Large Support
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.
(TCPL 201)
09:30 - 10:00 Dan Kral: Colorings of plane graphs
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.
(TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:00 Daniel Cranston: Coloring linegraphs of multigraphs with $\max(\omega, \lceil(5\Delta+3)/6\rceil)$ colors
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.
(TCPL 201)
11:00 - 12:00 Research in groups (TCPL)
12:00 - 13:30 Lunch (Vistas Dining Room)
14:30 - 15:00 Final progress reports (TCPL 201)
15:00 - 15:30 Coffee Break (TCPL Foyer)
15:30 - 17:00 Luke Postle: Tutorial: potential method (TCPL 201)
17:00 - 18:00 Free discussion and research in groups (TCPL)
18:00 - 19:30 Dinner (Vistas Dining Room)
Friday, October 21
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 10:00 Free discussion and research in groups (TCPL)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:30 Free discussion and research in groups (TCPL)
11:30 - 12:00 Checkout by Noon
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.
(Front Desk - Professional Development Centre)
12:00 - 13:30 Lunch from 11:30 to 13:30 (Vistas Dining Room)