A proof labelling scheme for a graph class C is an assignment of certificates to the vertices of any graph in the class C, such that upon reading its certificate and the certificates of its ...neighbors, every vertex from a graph G∈C accepts the instance, while if G∉C, for every possible assignment of certificates, at least one vertex rejects the instance. It was proved recently that for any fixed surface Σ, the class of graphs embeddable in Σ has a proof labelling scheme in which each vertex of an n-vertex graph receives a certificate of at most O(logn) bits. The proof is quite long and intricate and heavily relies on an earlier result for planar graphs. Here we give a very short proof for any surface. The main idea is to encode a rotation system locally, together with a spanning tree supporting the local computation of the genus via Euler's formula.
Graphs that are critical (minimal excluded minors) for embeddability in surfaces are studied. In Part I, it was shown that graphs that are critical for embeddings into surfaces of Euler genus k or ...for embeddings into nonorientable surface of genus k are built from 3-connected components, called hoppers and cascades. In Part II, all cascades for Euler genus 2 are classified. As a consequence, the complete list of obstructions of connectivity 2 for embedding graphs into the Klein bottle is obtained.
Let G be a 4-critical graph with t triangles, embedded in a surface of genus g. Let c be the number of 4-cycles in G that do not bound a 2-cell face. We prove that∑fface ofG(|f|−4)≤κ(g+t+c−1) for a ...fixed constant κ, thus generalizing and strengthening several known results. As a corollary, we prove that every triangle-free graph G embedded in a surface of genus g contains a set of O(g) vertices such that G−X is 3-colorable.
Grötzsch proved that every triangle-free planar graph is 3-colorable. Thomassen proved that every planar graph of girth at least five is 3-choosable. As for other surfaces, Thomassen proved that ...there are only finitely many 4-critical graphs of girth at least five embeddable in any fixed surface. This implies a linear-time algorithm for deciding 3-colorablity for graphs of girth at least five on any fixed surface. Dvořák, Král' and Thomas strengthened Thomassen's result by proving that the number of vertices in a 4-critical graph of girth at least five is linear in its genus. They used this result to prove Havel's conjecture that a planar graph whose triangles are pairwise far enough apart is 3-colorable. As for list-coloring, Dvořák proved that a planar graph whose cycles of size at most four are pairwise far enough part is 3-choosable.
In this article, we generalize these results. First we prove a linear isoperimetric bound for 3-list-coloring graphs of girth at least five. Many new results then follow from the theory of hyperbolic families of graphs developed by Postle and Thomas. In particular, it follows that there are only finitely many 4-list-critical graphs of girth at least five on any fixed surface, and that in fact the number of vertices of a 4-list-critical graph is linear in its genus. This provides independent proofs of the above results while generalizing Dvořák's result to graphs on surfaces that have large edge-width and yields a similar result showing that a graph of girth at least five with crossings pairwise far apart is 3-choosable. Finally, we generalize to surfaces Thomassen's result that every planar graph of girth at least five has exponentially many distinct 3-list-colorings. Specifically, we show that every graph of girth at least five that has a 3-list-coloring has 2Ω(n)−O(g) distinct 3-list-colorings.
We study the atomic embeddability testing problem, which is a common generalization of clustered planarity (c-planarity, for short) and thickenability testing, and present a polynomial-time algorithm ...for this problem, thereby giving the first polynomial-time algorithm for c-planarity. C-planarity was introduced in 1995 by Feng, Cohen, and Eades as a variant of graph planarity, in which the vertex set of the input graph is endowed with a hierarchical clustering and we seek an embedding (crossing free drawing) of the graph in the plane that respects the clustering in a certain natural sense. Until now, it has been an open problem whether c-planarity can be tested efficiently. The thickenability problem for simplicial complexes emerged in the topology of manifolds in the 1960s. A 2-dimensional simplicial complex is thickenable if it embeds in some orientable 3-dimensional manifold. Recently, Carmesin announced that thickenability can be tested in polynomial time. Our algorithm for atomic embeddability combines ideas from Carmesin’s work with algorithmic tools previously developed for weak embeddability testing. We express our results purely in terms of graphs on surfaces, and rely on the machinery of topological graph theory. Finally, we give a polynomial-time reduction from atomic embeddability to thickenability thereby showing that both problems are polynomially equivalent, and show that a slight generalization of atomic embeddability to the setting in which clusters are toroidal graphs is NP-complete.
A graph G is (d1,…,dk)‐colorable if its vertex set can be partitioned into k sets V1,…,Vk, such that for each i∈{1,…,k}, the subgraph of G induced by Vi has maximum degree at most di. The Four Color ...Theorem states that every planar graph is (0,0,0,0)‐colorable, and a classical result of Cowen, Cowen, and Woodall shows that every planar graph is (2,2,2)‐colorable. In this paper, we extend both of these results to graphs on surfaces. Namely, we show that every graph embeddable on a surface of Euler genus g>0 is (0,0,0,9g−4)‐colorable and (2,2,9g−4)‐colorable. Moreover, these graphs are also (0,0,O(g),O(g))‐colorable and (2,O(g),O(g))‐colorable. We also prove that every triangle‐free graph that is embeddable on a surface of Euler genus g is (0,0,O(g))‐colorable. This is an extension of Grötzsch's Theorem, which states that triangle‐free planar graphs are (0,0,0)‐colorable. Finally, we prove that every graph of girth at least 7 that is embeddable on a surface of Euler genus g is (0,O(g))‐colorable. All these results are best possible in several ways as the girth condition is sharp, the constant maximum degrees cannot be improved, and the bounds on the maximum degrees depending on g are tight up to a constant multiplicative factor.
A graph is (d1,...,dr)‐colorable if its vertex set can be partitioned into r sets V1,...,Vr so that the maximum degree of the graph induced by Vi is at most di for each i∈{1,...,r}. For a given pair ...(g,d1), the question of determining the minimum d2=d2(g,d1) such that planar graphs with girth at least g are (d1,d2)‐colorable has attracted much interest. The finiteness of d2(g,d1) was known for all cases except when (g,d1)=(5,1). Montassier and Ochem explicitly asked if d2(5, 1) is finite. We answer this question in the affirmative with d2(5,1)≤10; namely, we prove that all planar graphs with girth at least five are (1, 10)‐colorable. Moreover, our proof extends to the statement that for any surface S of Euler genus γ, there exists a K=K(γ) where graphs with girth at least five that are embeddable on S are (1, K)‐colorable. On the other hand, there is no finite k where planar graphs (and thus embeddable on any surface) with girth at least five are (0, k)‐colorable.
PDF
