Structural graph theory I
Org: Sophie Spirkl
(Princeton University, USA)
- JAMES DAVIES, University of Waterloo
Circle graphs are polynomially $\chi$-bounded [PDF]
We prove a polynomial $\chi$-bounding function for circle graphs. Joint work with Rose McCarty.
- SHENWEI HUANG, Wilfrid Laurier University
Colouring Square-Free Graphs without Long Induced Paths [PDF]
The Colouring problem is to decide if the vertices of a graph can be coloured with at most $k$ colours for a given integer $k$ such that no two adjacent vertices are coloured alike. In this talk, we show that Colouring is polynomial-time solvable for $(C_4,P_6)$-free graphs. Our algorithm is based on a novel decomposition theorem for $(C_4,P_6)$-free graphs without clique cutsets into homogeneous pairs of sets and a new framework for bounding the clique-width of a graph by the clique-width of its subgraphs induced by homogeneous pairs of sets. We also prove that Colouring is NP-complete for $(C_4,P_9)$-free graphs.
- CHUN-HUNG LIU, Texas A&M University
Threshold probability for destroying large minimum degree subgraphs of an H-minor free graph [PDF]
Fix a graph $H$ and an integer $d$, we consider the threshold $p(n)$ such that a random subgraph of an $H$-minor-free $n$-vertex graph obtained by keeping each edge with probability $p(n)$ contains a subgraph of minimum degree at least $d$. Determining such threshold for all pairs $(H,d)$ is difficult as it gives a constant-factor approximation for $\max_G|E(G)|$ for $H$-minor-free $n$-vertex graphs $G$ for any $H$. Joint with Wei, we determine such threshold asymptotically for a large set of pairs $(H,d)$ by proving a structural theorem for H-minor-free graphs which generalizes a result of Ossona de Mendez et. al.
- PIOTR MICEK, Jagiellonian University
Separating tree-chromatic number from path-chromatic number [PDF]
We apply Ramsey tools for trees to show that there is a family of graphs
which have the tree-chromatic number at most 2 while the path-chromatic
number is unbounded. This resolves a problem posed by Seymour.
(joint work with Fidel Barrera-Cruz, Stefan Felsner, Tamás Mészáros,
Heather Smith, Libby Taylor, and William T. Trotter)
- DAVID WOOD, Monash University
The product structure of minor-closed classes [PDF]
We prove that every planar graph is a subgraph of the strong
product of a path with some graph of bounded treewidth. This results
leads to proofs of the conjecture of
Heath, Leighton and Rosenberg (1992) that planar graphs have bounded
queue-number, and the conjecture of Alon, Grytczuk, Haluszczak and
Riordan (2002) that planar graphs have bounded nonrepetitive chromatic
number. These results generalise for graphs of bounded Euler genus and
graphs excluding a fixed minor. We also obtain a simple proof of the
result by DeVos, Ding, Oporowski, Sanders, Reed, Seymour and Vertigan
(2004), which says that graphs excluding a fixed minor have low
treewidth colourings. This is joint work with Vida Dujmović,
Gwenaël Joret, Piotr Micek, Pat Morin and Torsten Ueckerdt
[arXiv:1904.04791] and Vida Dujmović, Louis Esperet, Gwenaël Joret
and Bartosz Walczak [arXiv:1904.05269].