Schedule for: 21w5513 - New Perspectives in Colouring and Structure (Online)

We will briefly review the main properties of graphs and matrices with bounded twin-width, and then focus on two topics:
i) How to construct classes of graphs with unbounded twin-width which are small (growth $c^n.n!$). Can we make this construction explicit?
ii) Does forbidding induced subdivisions of cubic graphs lead to bounded twin-width in the sparse case? Proof for some particular cases.
The main challenge behind is of course to find some weak dual to twin-width certifying that a class has indeed unbounded twin-width.
Joint work with: E. Bonnet, C. Geniet, U. Giocanti, E.J. Kim, P. Ossona de Mendez, A. Reinald, P. Simon, Szymon Torunczyk, R. Watrigant.

Thomassen recently disproved his conjecture that triangle-free planar graphs have exponentially many colorings. We present an improved upper bound and give a supporting evidence towards the conjecture that it could be tight. Joint work with Luke Postle.

For a graph class $F$, let $ex_{F}(n)$ denote the maximum number of edges in an $n$-vertex graph in $F$. Jointly with Rohan Kapapia, we've proved that  $ex_{F}(n)$ is a sum of a linear function and an eventually periodic function for every proper minor-closed graph class $F$. We will discuss the proof and consequences of this theorem and related  open questions. 

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t ≥ 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t (\log t)^{0.5})$ and hence is $O(t (\log t)^{0.5})$-colorable. In a recent breakthrough, Norin, Song, and I proved that every graph with no $K_t$ minor is $O(t \log t)^c)$-colorable for every $c > 0.25$. Subsequently I showed that every graph with no $K_t$ minor is $O(t (\log\log t)^6)$-colorable.
We improve upon this further by showing that every graph with no $K_t$ minor is $O(t \log \log t)$-colorable. Our main technical result yields this as well as a number of other interesting corollaries. A natural weakening of Hadwiger's Conjecture is the so-called Linear Hadwiger's Conjecture that every graph with no $K_t$ minor is $O(t)$-colorable. We prove that Linear Hadwiger's Conjecture reduces to small graphs. In 2003, Kühn and Osthus proved that Hadwiger’s Conjecture holds for graphs of girth at least five (provided that t is sufficiently large). In 2005, Kühn and Osthus extended this result to the class of $K_{s,s}$-free graphs for any fixed positive integer $s ≥ 2$. Along this line, we show that Linear Hadwiger's Conjecture holds for the class of $K_r$-free graphs for every fixed $r$. This is joint work with Michelle Delcourt.

Kempe changes were introduced in 1879 in an attempt to prove the 4-colour theorem. They are a convenient if not crucial tool to prove various colouring theorems. Here, we consider how to navigate from a colouring to another through Kempe changes. When is it possible? How fast?

I plan to survey a variety of problems and results on the structure of triangle-free graphs and extensions, discussing their relationship to major topics like Hadwiger’s conjecture, the graph removal lemma, the Erdős-Hajnal conjecture, Turán's theorem, and Ramsey goodness.

A weak diameter coloring of a graph $G$ is a coloring of the vertices such that every monochromatic component has bounded diameter, where the diameter is computed in $G$. In this talk we consider the smallest number $c$ such that the $r$-th power of any graph in a fixed graph class has a weak diameter coloring with $c$ colors for arbitrarily large $r$. This $c$ is equivalent to the asymptotic dimension of metric spaces. We will determine the smallest $c$ for every minor-closed family of graphs and for every graph class with bounded layered treewidth. Simple corollaries of these results solve some problems about Riemannian surfaces and geometric group theory and rediscover known results about clustered coloring of those classes with bounded maximum degree. Joint work with Bonamy, Bousquet, Esperet, Groenland, Pirot and Scott.

Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a countable planar graph that contains every countable planar graph as a subgraph). János Pach (1981) answered this question in the negative. We strengthen this result by showing that every countable graph that contains all countable planar graphs must contain (i) an infinite complete graph as a minor, and (ii) arbitrarily large complete graph subdivisions. $$ $$ On the other hand, we construct a countable graph that contains all countable planar graphs and has several key properties such as linear colouring numbers, linear expansion, and every finite $n$-vertex subgraph has $O(\sqrt{n})$ treewidth (which implies the Lipton-Tarjan separator theorem). The graph is the strong product of the universal treewidth-6 graph and a 1-way infinite path. The proof builds on the finite case due to Dujmović et al (2020), which has been the key tool in the solution of several open problems. More generally, for every fixed positive integer $t$ we construct a countable graph that contains every countable $K_t$-minor-free graph and has the above key properties. $$ $$ Our final contribution is a construction, based on chordal partitions, of a countable graph that contains every countable $K_t$-minor-free graph as an induced subgraph, has linear colouring numbers and linear expansion, and contains no subdivision of the countably infinite complete graph (implying (ii) is best possible). $$ $$ Joint work with Tony Huynh, Bojan Mohar, Robert Šámal and Carsten Thomassen [https://arxiv.org/abs/2109.00327]. 

The multi-commodity flow-cut gap is a fundamental parameter that affects the performance of several divide & conquer algorithms, and has been extensively studied for various classes of undirected graphs. It has been shown by Linial, London and Rabinovich and by Aumann and Rabani that for general $n$-vertex graphs it is bounded by $O(\log n)$ and the Gupta-Newman-Rabinovich-Sinclair conjecture asserts that it is $O(1)$ for any family of graphs that excludes some fixed minor.

We show that the multicommodity flow-cut gap on DIRECTED planar graphs is  $O(\log^3 n)$. This is the first sub-polynomial bound for any (nontrivial) family of directed graphs. We remark that for general directed graphs, it has been shown by Chuzhoy and Khanna that the gap is $\Omega(n^{1/7})$, even for directed acyclic graphs.
As a direct consequence of our result, we also obtain the first polynomial-time polylogarithmic-approximation algorithms for the Directed Non-Bipartite Sparsest-Cut, and the Directed Multicut problems for directed planar graphs, which extends the long-standing result for undirectd planar graphs by Rao in 1999 (with a slightly weaker bound).
At the heart of our result we construct low diameter partitions of directed planar graphs, which is a purely graph theoretical result.  We also investigate low-distortion quasimetric embeddings into directed $\ell_1$.
Joint work with Tasos  Sidiropoulos.

The talk will be a brief introduction to the field of local certification, which is a nice bridge between structural graph theory and distributed complexity theory.
In local certification, the goal is to allow the vertices of a graph to decide "locally" if they belong to some fixed class $F$. Each vertex is given a small certificate, and after collecting the certificates of its neighbors each vertex decides if the graph lies in $F$. If the graph is indeed in $F$, all vertices must accept the instance, while if the graph is not in $F$, at least one vertex has to reject the instance. The goal is to minimize the size of the certificates.
I will give a short proof that $n$-vertex planar graphs (and more generally graphs embeddable in a fixed surface) can be locally certified with $O(\log n)$ bits per vertex. The main open problem in the area is whether this extends to any proper minor-closed class. Joint work with Benjamin Lévêque.

An ordered graph is a graph equipped with a total order on the vertices; two edges of an ordered graph are crossing if their endpoints alternate in the order. Various cases of graphs with geometric representations motivate the following question: for which ordered graphs $H$ is the class of graphs excluding $H$ as an induced ordered subgraph $\chi$-bounded? We provide complete answers for connected ordered graphs $H$, for crossing-free ordered graphs $H$, and for all 4-vertex ordered graphs $H$. In particular, making use of a new construction of triangle-free high-chromatic graphs, we show that ordered stars are the only connected ordered graphs $H$ for which the class is $\chi$-bounded. (Joint work with Piotr Mikołajczyk.) We also survey other known results on $\chi$-boundedness of ordered graphs with excluded ordered patterns.

The Burling sequence is a sequence of triangle-free graphs of increasing chromatic number. Any graph which is an induced subgraph of a graph in this sequence is called a Burling graph. These graphs have attracted some attention because they have geometric representations and because they provide counter-examples to several conjectures about bounding the chromatic number in classes of graphs.
The goal of this talk is to provide new definitions of Burling graphs. Three of them are geometrical: they characterize Burling graphs as intersection graphs of various geometrical objects (line segments of the place, frame of the plane, axis-aligned boxes of $\mathbb{R}^3$). All these representations of Burling graphs were known. Our contribution is to add restrictions to the configurations of the geometrical objects so that there is an equivalence between the intersection graphs and the Burling graphs.
Among our new equivalent definitions of Burling graphs, one is of a more combinatorial flavour. It says how any Burling graph can be derived from a tree with some specific rules. This definition is convenient decide whether some given graph is Burling or not. We use it to give several generic examples of Burling graphs or rules to find edges whose subdivision preserves being a Burling graph. We also use it to find examples of graphs that are not Burling. Among several consequences of all this, one is that graphs that do not contain any subdivision of $K_5$ as an induced subgraph have unbounded chromatic number.
This is a joint work with Pegah Pournajafi.

Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until recently remained out of reach.
Tree decompositions are closely related to the existence of "laminar collections of separations" in a graph, which roughly means that the separations in the collection ``cooperate'' with each other, and the pieces that are obtained when the graph is simultaneously decomposed by all the separations in the collection ``line up'' to form a tree structure. Such collections of separations come up naturally in the context of forbidden minors.
In the case of families where induced subgraphs are excluded, while there are often natural separations, they are usually very far from forming a laminar collection. In what follows we mostly focus on families of graphs of bounded degree. It turns out that due to the bound on the degree, these collections of natural separations can be partitioned into a bounded number of laminar collections. This in turn allows to us obtain a wide variety of structural and algorithmic results, which we will survey in this talk.

I will talk about a recent proof that graphs excluding a fixed complete graph and a slightly extended set of three-path-configurations have treewidth logarithmic in their number of vertices. This proves a conjecture of Sintiari and Trotignon about (theta, triangle)-free graphs. Joint work with Tara Abrishami, Maria Chudnovsky, and Sepehr Hajebi.

Graph classes excluding a path or a subdivided claw as an induced subgraph are so far quite mysterious: on one hand, beside some corner cases, they do not seem to have any good structural description, but on the other hand, a number of combinatorial problems - including Maximum Independent Set (MIS) - lack an NP-hardness proof in these graph classes, indicating a possible hidden structure that can be used algorithmically. Furthermore, graphs excluding a fixed path as an induced subgraph were one of the earliest examples of a chi-bounded graph class, with an elegant proof technique dubbed the Gyárfás' path argument. In recent years the progress accelerated, leading to, among other results, (a) a quasi-polynomial time algorithm for MIS in graphs excluding a fixed path as an induced subgraph, (b) a QPTAS for MIS in graphs excluding a subdivided claw as an induced subgraph, (c) the proof of the Erdős-Hajnal property in graph classes excluding a fixed forest and its complement. In the talk, after a quick survey of these results, I will focus on the most recent developments - the quasi-polynomial time algorithms for MIS and related problems in P_t-free graphs.

For graphs $G$ and  $H$, we say that $G$ is $H$-free if it does not contain $H$ as an induced subgraph. Already in the early 1980s Alekseev observed that if $H$ is connected, then the Max Weight Independent Set problem (MWIS) remains NP-hard in $H$-free graphs, unless $H$ is a path or a subdivided claw, i.e., a graph obtained from the three-leaf star by subdividing each edge some number of times (possibly zero). Since then determining the complexity of MWIS in these remaining cases is one of the most important problems in algorithmic graph theory.
A general belief is that the problem is polynomial-time solvable, which is witnessed by algorithmic results for graphs excluding some small paths or subdivided claws. More conclusive evidence was given by the recent breakthrough result by Gartland and Lokshtanov [FOCS 2020]: They proved that MWIS can be solved in quasipolynomial time in $H$-free graphs, where $H$ is any fixed path. If $H$ is an arbitrary subdivided claw, we know much less: The problem admits a QPTAS and a subexponential-time algorithm [Chudnovsky et al., SODA 2019].
We make an important step towards solving the problem by showing that for any subdivided claw $H$, MWIS is polynomial-time solvable in $H$-free graphs of bounded degree.
The results are joint work with T. Abrishami, M. Chudnovsky, and C. Dibek.