CanaDAM 2021
En ligne, 25 - 28 mai 2021

Structures in Graphs

ALEXANDRE BLANCHÉ, LaBRI, Université de Bordeaux
Gallai's path decomposition conjecture for planar graphs  [PDF]

In 1968, Gallai conjectured that the edges of any connected graph with $n$ vertices can be partitioned into $\lceil \frac{n}{2} \rceil$ paths. Although this conjecture has been tackled and partially solved over the years, such as for graphs of maximum degree $5$ (Bonamy, Perrett, 2016), it is still open as of today. We prove that the conjecture is true for every planar graph. More precisely, we show that every connected planar graph except $K_3$ and $K_5^-$ ($K_5$ minus one edge) can be decomposed into $\lfloor \frac{n}{2} \rfloor$ paths. (Joint work with Marthe Bonamy and Nicolas Bonichon)

CARL FEGHALI, Charles University
Decomposing a triangle-free planar graph into a forest and a subcubic forest  [PDF]

We strengthen a result of Dross, Montassier and Pinlou (2017) that the vertex set of every triangle-free planar graph can be decomposed into a set that induces a forest and a set that induces a forest with maximum degree at most $5$, showing that $5$ can be replaced by $3$. This is joint work with Robert \v{S}\'amal.

Stack-number is not bounded by queue-number  [PDF]

Stacks and queues are fundamental data structures in computer science, but which is more powerful? In 1992, Heath, Leighton and Rosenberg formulated an approach to answer this question by introducing the graph parameters stack-number and queue-number to respectively measure the power of stacks and queues for representing graphs. Stacks would be considered more powerful than queues if every class of graphs with bounded queue-number has bounded stack-number and the converse does not hold (and vice versa). Despite extensive research on these parameters for various graph classes, this question has remained unsolved. In this talk, I will present a family of graphs that have queue-number at most 4 but unbounded stack-number. This demonstrates that stacks are not more powerful than queues in representing graphs. It remains open whether queues are more powerful than stacks. This talk is based on joint work with Vida Dujmović, David Eppstein, Pat Morin and David Wood.

TOMÁŠ KAISER, University of West Bohemia
Edge-critical subgraphs of Schrijver graphs  [PDF]

For $k\geq 1$ and $n\geq 2k$, the Kneser graph $\mathrm{KG}(n,k)$ has all $k$-element subsets of an $n$-element set as its vertices, with edges joining disjoint subsets. Lovász (1978) proved that the chromatic number of $\mathrm{KG}(n,k)$ is $n-2k+2$. Schrijver (1978) described a subgraph of this graph, now called the Schrijver graph $\mathrm{SG}(n,k)$, with the same chromatic number and the property of being vertex-critical (which means that the chromatic number decreases if any vertex is deleted).

We take the next step in this direction and give an explicit combinatorial description of an edge-critical spanning subgraph of $\mathrm{SG}(n,k)$, for all values of $n,k$ as above, with chromatic number $n-2k+2$. Here, a graph is edge-critical if the deletion of any edge decreases the chromatic number. Joint work with Matěj Stehlík.