CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

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].