|
|||||
Graph decompositions
Org: Marthe Bonamy (Laboratoire Bordelais de Recherche en Informatique, France)
[PDF]
Org: Marthe Bonamy (Laboratoire Bordelais de Recherche en Informatique, France)
[PDF]
- FÁBIO BOTLER, Universidade Federal do Rio de Janeiro
Gallai's Conjecture for Triangle-Free Planar Graphs [PDF]
-
Gallai (1968) conjectured that every connected graph on \(n\) vertices can be decomposed into at most \(\lfloor (n+1)/2\rfloor\) paths. Lovász (1968) verified this conjecture for graphs with at most one vertex with even degree, and Pyber (1996) verified it for graphs in which every cycle contains a vertex with odd degree. Recently, Bonamy and Perrett (2016) verified Gallai's Conjecture for graphs with maximum degree at most \(5\), and Botler et al. (2017) verified it for graphs with treewidth at most \(3\). In this work, we verify Gallai's Conjecture for triangle-free planar graphs.
- DANIEL CRANSTON, Virginia Commonwealth University
Circular Coloring of Planar Graphs [PDF]
-
For integers $a\ge 2b>0$, a circular $a/b$-flow takes values from $\{\pm b, \pm(b+1), \dots, \pm(a-b)\}$. We prove that (i) every $10$-edge-connected planar graph admits a circular $5/2$-flow and (ii) every $16$-edge-connected planar graph admits a circular $7/3$-flow. Statement (i) was previously proved by Dvo\v{r}\'{a}k and Postle, but our proof is much shorter and avoids using computers for case-checking. Further, it has new implications for antisymmetric flows. Statement (ii) is especially interesting because of known $12$-edge-connected nonplanar graphs that admit no circular $7/3$-flow. Thus, the planarity hypothesis of (ii) is essential. This work is joint with Jiaao Li, Nankai University, China.
- TOM KELLY, University of Waterloo
Fractional Coloring with Local Demands [PDF]
-
In fractional coloring, we assign vertices of a graph subsets of the $[0, 1]$-interval and adjacent vertices receive disjoint subsets. We investigate fractional colorings where vertices ``demand'' varying amounts of color, determined by local parameters such as the degree of a vertex. Many well-known results concerning the fractional chromatic number and independence number have natural generalizations in this new paradigm. We discuss several such results as well as open problems. In particular, we prove a ``local demands'' version of Brooks' Theorem that considerably generalizes the Caro-Wei Theorem and implies new bounds on the independence number. Joint work with Luke Postle.
- NATASHA MORRISON, University of Cambridge and IMPA
Partitioning the vertices of a torus into isomorphic subgraphs [PDF]
-
Let $H$ be an induced subgraph of the torus $C_k^n$. We discuss results concerning when the vertices or edges of $C_k^n$ can be decomposed into induced copies of $H$. In particular, we disprove a conjecture of Gruslys, showing that when $k$ is
odd and not a prime power, then there exists $H$ such that $|V(H)|$ divides
some power of $k$, but there is no $n$ such that the vertices of $C_k^n$ can be decomposed into copies of $H$. We also disprove a conjecture of Gruslys,
Leader and Tan on edge decomposing $C_k^n$. Joint work with Marthe Bonamy and Alex Scott.