Mathematical Research Seminar - Archive
| 2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
Hoang La, Borut Lužar, Kenny Štorgel
The Grötzsch Theorem states that every triangle-free planar graph G admits a proper 3-coloring, i.e. a coloring of the vertices of G with three colors such that adjacent vertices are assigned distinct colors. However, we may also allow triangles in general planar graphs and still retain 3-colorability. Havel conjectured that a 3-colorable planar graph may contain arbitrarily many triangles as long as they are su ciently far apart. This conjecture was proved by Dvořák, Král', and Thomas. On the other hand, there are 3-colorable planar graphs that may have close triangles (even incident). A result by Dross et al. states that every planar graph obtained as a subgraph of the medial graph of a bipartite plane graph is 3-colorable.
As mentioned, the Grötzsch Theorem has many generalizations, although, perhaps the most well-known is a result of Grünbaum and Aksenov, giving 3-colorability of planar graphs with at most three triangles, which is in general best possible. A lot of attention was also given to extending 3-colorings of subgraphs of triangle-free planar graphs to the whole graph. In particular, a result of Aksenov, Borodin, and Glebov states that we can precolor any two non-adjacent vertices in a triangle-free planar graph and retain 3-colorability. Furthermore, several other results exist which deal with precolorings of a face of certain length in a triangle-free planar graph.
In this talk, we will present the above-mentioned results and provide further extensions of the Grötzsch Theorem by considering 3-colorings of planar graphs with at most one triangle. In particular, we show that a precoloring of any two non-adjacent vertices and a precoloring of a face of length at most 4 can be extended to a 3-coloring of the whole graph. Additionally, we show that for every vertex of degree at most 3 in a planar graph with at most one triangle, a precoloring of its neighborhood with the same color extends to a 3-coloring of the whole graph. The latter result yields an a rmative answer to a conjecture on adynamic coloring.
Our Math Research Seminar will not be broadcasted via Zoom this time.
See you there!
Everyone is welcome and encouraged to attend.
In 1976, Bondy and Chvátal [Discrete Math. 1976] introduced the notion of closure of a graph: let $\ell$ be an integer; the $(n+\ell)$-closure, $cl_{n+\ell}(G)$, of a graph $G$ with $n$ vertices is obtained from $G$ by recursively adding an edge between pairs of nonadjacent vertices whose degree sum is at least $n+\ell$ until no such pair remains.
A graph property $\Upsilon$ defined on all graphs of order $n$ is said to be $(n+\ell)$-stable if for any graph $G$ of order $n$ that does not satisfy $\Upsilon$, the fact that $uv$ is not an edge of $G$ and that $G+uv$ satisfies $\Upsilon$ implies $d(u)+d(v)< n+\ell$.
The degeneracy of a graph $G$ is the least $k$ such that every induced subgraph of $G$ contains a vertex with degree at most $k$.
In this talk, we present an algorithmic framework based on the notion of Bondy and Chvátal closures to deal with the degeneracy of the complement graph, called co-degeneracy, as a parameter. Using such a framework, we can show that Hamiltonian Path, Hamiltonian Cycle, and Minimum Path Cover can be solved efficiently on graphs with bounded co-degeneracy.
In addition, we show that Edge Dominating Set can also be solved efficiently on this class of graphs.
Finally, by determining the stability of the property of having a bounded cycle cover and combining our framework with some results of Jansen et al. [WG 2019], we show an efficient algorithm for Minimum Cycle Cover on graphs with bounded co-degeneracy.
These results show that co-degeneracy is a useful width parameter for handling dense instances of graph problems.
Everyone is welcome and encourage to attend.
