Hyperbolic families and coloring graphs on surfaces
By Luke Postle and Robin Thomas
Abstract
We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $G$ be a graph embedded in a fixed surface $\Sigma$ of genus $g$ and let $L=(L(v):v\in V(G))$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $G$ is triangle-free, or each list has size at least three and $G$ has no cycle of length four or less. An $L$-coloring of $G$ is a mapping $\phi$ with domain $V(G)$ such that $\phi (v)\in L(v)$ for every $v\in V(G)$ and $\phi (v)\ne \phi (u)$ for every pair of adjacent vertices $u,v\in V(G)$. We prove
•
if every non-null-homotopic cycle in $G$ has length $\Omega (\log g)$, then $G$ has an $L$-coloring,
•
if $G$ does not have an $L$-coloring, but every proper subgraph does (“$L$-critical graph”), then $|V(G)|=O(g)$,
•
if every non-null-homotopic cycle in $G$ has length $\Omega (g)$, and a set $X\subseteq V(G)$ of vertices that are pairwise at distance $\Omega (1)$ is precolored from the corresponding lists, then the precoloring extends to an $L$-coloring of $G$,
•
if every non-null-homotopic cycle in $G$ has length $\Omega (g)$, and the graph $G$ is allowed to have crossings, but every two crossings are at distance $\Omega (1)$, then $G$ has an $L$-coloring,
•
if $G$ has at least one $L$-coloring, then it has at least $2^{\Omega (|V(G)|)}$ distinct $L$-colorings.
We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities.
1. Introduction
All graphs in this paper are finite, and have no loops or multiple edges. Our terminology is standard, and may be found in Reference 11 or Reference 18. In particular, cycles and paths have no repeated vertices, and by a coloring of a graph $G$ we mean a proper vertex-coloring; that is, a mapping $\phi$ with domain $V(G)$ such that $\phi (u)\ne \phi (v)$ whenever $u,v$ are adjacent vertices of $G$. By a surface we mean a (possibly disconnected) compact $2$-dimensional manifold with possibly empty boundary. The boundary of a surface $\Sigma$ will be denoted by bd$(\Sigma )$. By the classification theorem every surface $\Sigma$ is obtained from the disjoint union of finitely many spheres by adding $a$ handles, $b$ crosscaps and removing the interiors of finitely many pairwise disjoint closed disks. In that case the Euler genus of $\Sigma$ is $2a+b$.
Motivated by graph coloring problems we study families of graphs that satisfy the following isoperimetric inequalities. By an embedded graph we mean a pair $(G,\Sigma )$, where $\Sigma$ is a surface without boundary and $G$ is a graph embedded in $\Sigma$. We will usually suppress the surface and speak about an embedded graph $G$, and when we will need to refer to the surface we will do so by saying that $G$ is embedded in a surface $\Sigma$. Let $\mathcal{F}$ be a family of non-null embedded graphs. We say that $\mathcal{F}$ is hyperbolic if there exists a constant $c>0$ such that if $G\in \mathcal{F}$ is a graph that is embedded in a surface $\Sigma$, then for every closed curve $\xi :{\mathbb{S}}^1\to \Sigma$ that bounds an open disk $\Delta$ and intersects $G$ only in vertices, if $\Delta$ includes a vertex of $G$, then the number of vertices of $G$ in $\Delta$ is at most $c(|\{x\in {\mathbb{S}}^1\,:\, \xi (x)\in V(G)\}|-1)$. We say that $c$ is a Cheeger constant for $\mathcal{F}$.
The hyperbolic families of interest to us arise from coloring problems, more specifically from a generalization of the classical notion of coloring, introduced by Erdős, Rubin, and Taylor Reference 32 and known as list-coloring or choosability. We need a few definitions in order to introduce it. Let $G$ be a graph and let $L=(L(v):v\in V(G))$ be a collection of lists. If each set $L(v)$ is non-empty, then we say that $L$ is a list-assignment for $G$. If $k$ is an integer and $|L(v)|\ge k$ for every $v\in V(G)$, then we say that $L$ is a $k$-list-assignment for $G$. An $L$-coloring of $G$ is a mapping $\phi$ with domain $V(G)$ such that $\phi (v)\in L(v)$ for every $v\in V(G)$ and $\phi (v)\ne \phi (u)$ for every pair of adjacent vertices $u,v\in V(G)$. Thus if all the lists are the same, then this reduces to the notion of coloring. We say that a graph $G$ is $k$-choosable, also called $k$-list-colorable, if $G$ has an $L$-coloring for every $k$-list-assignment$L$. The list chromatic number of $G$, denoted by $ch(G)$, also known as choosability, is the minimum $k$ such that $G$ is $k$-list-colorable. A graph $G$ is $L$-critical if $G$ is not $L$-colorable, but every proper subgraph of $G$ is. To capture the three most important classes of coloring problems to which our theory applies, let us say that a list-assignment $L$ for a graph $G$ is of type $345$ or a type $345$ list-assignment if either
•
$L$ is a $5$-list-assignment, or
•
$L$ is a $4$-list-assignment and $G$ is triangle-free, or
•
$L$ is a $3$-list-assignment and $G$ has no cycle of length four or less.
We are now ready to describe the three most interesting hyperbolic families of graphs.
Theorem 1.1 is a special case of the more general Theorem 3.6, also stated as Theorem 8.8 and proved in Section 8. Additional examples of hyperbolic families are given in Section 5. We study hyperbolic families in Section 6. Corollary 6.21 implies the following. A family $\mathcal{F}$ of embedded graphs is closed under curve cutting if for every embedded graph $(G,\Sigma )\in \mathcal{F}$ and every simple closed curve $\xi$ in $\Sigma$ whose image is disjoint from $G$, if $\Sigma '$ denotes the surface obtained from $\Sigma$ by cutting open along $\xi$ and attaching disk(s) to the resulting curve(s), then the embedded graph $(G,\Sigma ')$ belongs to $\mathcal{F}$.
We prove Theorem 1.2 immediately after Corollary 6.21.
Theorem 1.2 is already quite useful. For instance, by Theorem 1.1 it implies the first result stated in the abstract. Our main theorem about hyperbolic families is Theorem 6.28, which describes their structure. Roughly speaking, it says that every member of a hyperbolic family on a fixed surface can be obtained from a bounded size graph by attaching “narrow cylinders”. The theorem suggests the following strengthening of hyperbolicity. Let $G$ be a member of a hyperbolic family $\mathcal{F}$ embedded in a surface $\Sigma$, and let $\Lambda \subseteq \Sigma$ be a cylinder such that the two boundary components of $\Lambda$ are cycles $C_1,C_2$ of $G$. If for all $G$ and $\Lambda$ the number of vertices of $G$ in $\Lambda$ is bounded by some function of $|V(C_1)|+|V(C_2)|$, then we say that $\mathcal{F}$ is strongly hyperbolic. Theorem 3.6 implies that the families from Theorem 1.1 are, in fact, strongly hyperbolic.
We study strongly hyperbolic families in Section 7. The following is a special case of Theorem 7.11.
By applying Theorem 1.3 to the families from Theorem 1.1 we deduce the second result stated in the abstract. To prove the next result in the abstract we need to extend the notion of hyperbolicity to rooted graphs. A rooted graph is a pair $(G,X)$, where $G$ is a graph and $X\subseteq V(G)$. We extend all the previous terminology to rooted graphs in the natural way, so we can speak about rooted embedded graphs. The definitions of hyperbolicity and strong hyperbolicity extend to rooted graphs with the proviso that the disk $\Delta$ and cylinder $\Lambda$ contain no member of $X$ in their interiors. Now we can state a more general special case of Theorem 7.11. A proof is given immediately after Theorem 7.11.
By applying Theorem 1.4 to the rooted versions of the families from Theorem 1.1 we deduce the following theorem, which we state and formally prove in a slightly more general form as Theorem 3.19.
Theorem 1.5 proves the third result stated in the abstract. The fourth result follows similarly (formally we prove it as Theorem 3.21), but it requires a generalization of the above two theorems to embedded graphs with a set of distinguished cycles. That is why we will introduce the notion of embedded graphs with rings in Section 3, where a ring is a cycle or a complete graph on at most two vertices. The last result mentioned in the abstract needs the strong hyperbolicity of a different family of embedded graphs. It follows from Theorem 3.22.
The paper is organized as follows. In Section 2 we survey results on list coloring graphs on surfaces. In Section 3 we formulate Theorem 3.8, our main coloring result, and derive a number of consequences from it, assuming a generalization of Theorem 1.1, stated as Theorem 3.6, which we do not prove until Section 8. Theorem 3.8 is an easy consequence of Theorem 7.11, our main result about strongly hyperbolic families. In the short Section 4 we prove a lemma about exponentially many extensions of a coloring of a facial cycle in a planar graph. In Section 5 we present examples of hyperbolic families. We investigate their structure in depth in Section 6, where the main result is Theorem 6.28, giving structural information about members of a hyperbolic family. In Section 7 we give examples of strongly hyperbolic families and investigate their structure. The main theorem is Theorem 7.11, but there is also the closely related Theorem 7.12. The latter eliminates an outcome of the former at the expense of a worse bound. In the final Section 8 we complete the proof of the strong hyperbolicity of the three main families of interest (a.k.a. a generalization of Theorem 1.1), and prove Theorem 3.8. We also formulate and prove the closely related Theorem 8.12, which has an identical proof, using Theorem 7.12 instead of Theorem 7.11.
2. Survey of coloring graphs on surfaces
In this section we survey the main results about coloring graphs on surfaces in order to place our work in a historical context. However, familiarity with this section is not required in order to understand the rest of the paper.
2.1. Coloring graphs on surfaces
The topic of coloring graphs on surfaces dates back to 1852, when Francis Guthrie formulated the Four Color Conjecture, which has since become the Four Color Theorem Reference 7Reference 8Reference 54. Even though this theorem, its history and ramifications are of substantial interest, we omit any further discussion of it, because our primary interest lies in surfaces other than the sphere. Thus we skip to the next development, which is the well-known Heawood formula from 1890, asserting that a graph embedded in a surface $\Sigma$ of Euler genus $g\ge 1$ can be colored with at most $H(\Sigma ):=\lfloor (7 + \sqrt {24g + 1})/2\rfloor$ colors. This formula is actually a fairly easy concequence of Euler’s formula. It turned out that the bound it gives is best possible for every surface except the Klein bottle, but that was not established until the seminal work of Ringel and Youngs Reference 53 in the 1960s. Franklin Reference 33 proved that every graph embeddable in the Klein bottle requires only six colors, whereas Heawood’s bound predicts seven. Dirac Reference 19 and Albertson and Hutchinson Reference 3 improved Heawood’s result by showing that every graph in $\Sigma$ is actually $(H(\Sigma )-1)$-colorable, unless it has a subgraph isomorphic to the complete graph on $H(\Sigma )$ vertices.
Thus the maximum chromatic number for graphs embeddable in a surface has been determined for every surface. However, a more modern approach to coloring graphs on surfaces, initiated by Thomassen in the 1990s, is based on the observation that only very few graphs embedded in a fixed surface $\Sigma$ have chromatic number close to $H(\Sigma )$; in fact, as we are about to see, most have chromatic number at most five. To make this assertion precise, we need a definition. Let $t\ge 2$ be an integer. We say that a graph $G$ is $t$-critical if it is not $(t-1)$-colorable, but every proper subgraph of $G$ is $(t-1)$-colorable. Using Euler’s formula, Dirac Reference 20 proved that for every $t\ge 8$ and every surface $\Sigma$ there are only finitely many $t$-critical graphs that embed in $\Sigma$. By a result of Gallai Reference 36, this can be extended to $t = 7$. We will see in a moment that this extends to $t=6$ by a deep result of Thomassen. First however, let us mention a predecessor of this theorem, also due to Thomassen Reference 55.
The following related result was obtained by Fisk and Mohar Reference 35.
The other theorem of Thomassen Reference 60 reads as follows.
It is clear that Theorem 2.3 implies Theorem 2.1, but we state them separately for two reasons. One is historical, and the other is that we will be able to improve the bound on $\gamma$ in Theorem 2.1 to an asymptotically best possible value, and that version is no longer a consequence of Theorem 2.3. Theorem 2.3 immediately implies a polynomial-time algorithm for deciding whether a graph on a fixed surface is $5$-colorable. By a result of Eppstein Reference 31 there is, in fact, a linear-time algorithm, as follows.
Corollary 2.4 guarantees the existence of an algorithm. To construct an algorithm we would need to find the list of all the $6$-critical graphs that can be embedded in $\Sigma$. Such lists are known only for the projective plane Reference 3, the torus Reference 56, and the Klein bottle Reference 14Reference 43. However, the proof of Theorem 2.3 can be converted to a finite-time algorithm that will output the desired list; thus the algorithm, even though not explicitly known, can be constructed in finite-time.
Theorem 2.3 is best possible as it does not extend to $5$-critical graphs. Indeed, Thomassen Reference 60, using a construction of Fisk Reference 34, constructed infinitely many $5$-critical graphs that embed in any given surface other than the sphere. The next logical question then is whether Corollary 2.4 holds for $3$- or $4$-coloring. For $3$-coloring the answer is no, unless P=NP, because $3$-colorability of planar graphs is one of the original NP-complete problems of Garey and Johnson Reference 37. For $4$-coloring there is a trivial algorithm when $\Sigma$ is the sphere by the Four Color Theorem, and for all other surfaces it is an open problem. Given the difficulties surrounding the known proofs of the Four Color Theorem, the prospects for a resolution of that open problem in the near future are not very bright.
A classical theorem of Grötzsch Reference 39 asserts that every triangle-free planar graph is $3$-colorable. Thomassen Reference 58Reference 59Reference 61 found three reasonably short proofs, and extended the theorem to the projective plane and the torus. However, for the extensions to hold one has to assume that the graph has no cycles of length at most four. Those results prompted Thomassen to formulate the following research program. First, let us recall that the girth of a graph is the maximum integer $q$ (or infinity) such that every cycle has length at least $q$. Thomassen asked for which pairs of integers $k$ and $q$ is it the case that for every surface $\Sigma$ there are only finitely many $(k+1)$-critical graphs of girth at least $q$ in $\Sigma$. If the answer is positive, then $k$-colorability of graphs of girth at least $q$ in $\Sigma$ can be tested in linear time. If the answer is negative, then there is still the question whether the $k$-colorability of graphs of girth at least $q$ in $\Sigma$ can be tested in polynomial-time.
These questions have now been resolved, except for the already mentioned case $k=4$ and $q=3$. Let us briefly survey the results. It is fairly easy to see that for every surface $\Sigma$ there are only finitely many $(k+1)$-critical graphs of girth at least $q$ in $\Sigma$ whenever either $q\ge 6$, or $q\ge 4$ and $k\ge 4$, or $k\ge 6$. Theorem 2.3 states that this also holds when $k=5$, and the following deep theorem, also due to Thomassen Reference 62, says that it also holds when $k=3$ and $q=5$.
Dvořák, Král’, and Thomas strengthened this theorem by giving an asymptotically best possible bound on the size of the $4$-critical graphs, as follows.
Thus the only case we have not yet discussed is $k=3$ and $q=4$; that is, $3$-coloring triangle-free graphs on a fixed surface. There are infinitely many $4$-critical triangle-free graphs on any surface other than the sphere, but, nevertheless, $3$-colorability of triangle-free graphs on any fixed surface can be tested in polynomial time Reference 24Reference 28. However, this algorithm requires different methods. The theory we develop in this paper does not seem to apply to $3$-coloring triangle-free graphs.
2.2. List-coloring graphs on surfaces
Our main topic of interest is list coloring, a generalization of ordinary vertex-coloring, introduced in the Introduction. List coloring differs from regular coloring in several respects. One notable example is that the Four Color Theorem does not generalize to list-coloring. Indeed, Voigt Reference 66 constructed a planar graph that is not $4$-choosable. On the other hand Thomassen Reference 57 proved the following remarkable theorem with an outstandingly short and beautiful proof.
The following theorem was also proven by Thomassen, first in Reference 59 and later he found a shorter proof in Reference 61.
The corresponding theorem that every planar graph of girth at least four is $4$-choosable is an easy consequence of Euler’s formula; a slightly stronger version of it is part of Theorem 2.14 below. For later reference we need the following small generalization of the last three results mentioned. It follows easily from known results. A graph has crossing number at most one if it can be drawn in the plane such that at most one pair of edges cross.
Let us recall that if $L$ is a list-assignment for a graph $G$, then we say that $G$ is $L$-critical if $G$ does not have an $L$-coloring but every proper subgraph of $G$ does. Thomassen Reference 60, Theorem 4.4 proved the following theorem.
A proof of Conjecture 2.11 was announced by Kawarabayashi and Mohar Reference 44, but no proof appeared so far. We give a proof of Conjecture 2.11 in Theorem 3.11 below. Meanwhile, DeVos, Kawarabayashi, and Mohar Reference 17 generalized Theorem 2.1 to list-coloring.
In Theorem 3.9 we give an independent proof of Theorem 2.12 with an asymptotically best possible bound on $\gamma$.
Kawarabayashi and Thomassen Reference 45 proved that Theorem 2.7 “linearly extends” to higher surfaces, as follows.
We give an alternate proof of Theorem 2.13 (admittedly with a worse constant) and extend it to other coloring problems in Theorem 3.17.
2.3. Extending precolored subgraphs
An important proof technique is to extend a coloring of a subgraph to the entire graph. We will need the following result.
Theorem 2.14 obviously does not extend to arbitrarily long paths. However, in Reference 51 we have shown the following. By an outer cycle in a plane graph we mean the cycle bounding the outer face (the unique unbounded face).
Earlier versions of this theorem were proved for ordinary coloring by Thomassen Reference 60, Theorem 5.5, who proved it with ${19}|V(C)|$ replaced by $5^{|V(C)|^3}$, and by Yerger Reference 67, who improved the bound to $O(|V(C)|^3)$. If every vertex of $G\setminus V(C)$ has degree at least five and all its neighbors in $G$ belong to $C$, then the only graph $H$ satisfying the conclusion of Theorem 2.15 is the graph $G$ itself. It follows that the bound in Theorem 2.15 is asymptotically best possible.
Theorem 2.15 was a catalyst that led to this paper, because it motivated us to introduce the notion of a hyperbolic family of embedded graphs and to develop the theory presented here. It is an easy consequence of Theorem 2.15, and we show it formally in Theorem 5.3, that the family of embedded graphs that are $L$-critical for some $5$-list-assignment is hyperbolic.
An analog of Theorem 2.15 for graphs of girth at least five and $3$-list-assignments was obtained by Dvořák and Kawarabayashi Reference 22, Theorem 5.
Let us remark that, unlike the previous two results, the corresponding theorem for graphs of girth at least four and $4$-list-assignments is a fairly easy consequence of Euler’s formula. We state it here for future reference. It follows from Lemma 5.10.
Thomassen conjectured Reference 60 that if $S$ is a set of vertices of a planar graph $G$ and any two distinct members of $S$ are at least some fixed distance apart, then any precoloring of $S$ extends to a $5$-coloring of $G$. Albertson Reference 2 proved this in 1998, and conjectured that it generalizes to $5$-list-coloring. Albertson’s conjecture was recently proved by Dvořák, Lidický, Mohar, and Postle Reference 30, as follows.
Albertson and Hutchinson Reference 4 have generalized Albertson’s result to other surfaces. They proved that if the graph is locally planar, then any precoloring of vertices far apart extends.
Meanwhile, Dean and Hutchinson Reference 16 have proven that if $G$ is a graph embedded in a surface $\Sigma$,$L$ is an $H(\Sigma )$-list-assignment for $V(G)$, and $X\subset V(G)$ such that all distinct vertices $u, v\in X$ have pairwise distance at least four, then any $L$-coloring of $X$ extends to an $L$-coloring of $G$. They also asked whether their result extends to lists of other sizes. We restate their question as follows.
In Theorem 3.19 we give an independent proof of a common generalization of Theorems 2.18 and 2.19, which also answers Question 2.20.
We say a graph $G$ is drawn in a surface $\Sigma$ if $G$ is embedded in $\Sigma$ except that there are allowed to exist points in $\Sigma$ where two—but only two—edges cross. We call such a point of $\Sigma$ and the subsequent pair of edges of $G$, a crossing. Dvořák, Lidický, and Mohar Reference 29 proved that crossings far apart instead of precolored vertices also leads to $5$-list-colorability. The distance between the crossing of the edge $u_1v_1$ with the edge $x_1y_1$ and the crossing of the edge $u_2v_2$ with the edge $x_2y_2$ is the length of the shortest path in $G$ with one end in the set $\{u_1,v_1,x_1,y_1\}$ and the other end in the set $\{u_2,v_2,x_2,y_2\}$.
In Theorem 3.21 we give an independent proof of Theorem 2.21 (but with a worse constant) and generalize it to arbitrary surfaces.
2.4. Coloring with short cycles far apart
Earlier we mentioned the classical theorem of Grötzsch Reference 39 that every triangle-free planar graph is $3$-colorable. Aksenov Reference 1 proved that the same is true even if the graph is allowed to have at most three triangles. Havel Reference 40 asked whether there exists an absolute constant $D$ such that if every two triangles in a planar graph are at least distance $D$ apart, then the graph is $3$-colorable. Havel’s conjecture was proved in Reference 27. The conjecture cannot be extended to $3$-list-coloring verbatim, because there exist triangle-free planar graphs that are not $3$-list-colorable. However, Dvořák Reference 21 proved the following.
We give a different proof of and generalize Dvořák’s result to locally planar graphs on surfaces in Theorem 3.20.
2.5. Exponentially many colorings
It is an easy consequence of the Four Color Theorem that every planar graph has exponentially many $5$-colorings. Birkhoff and Lewis Reference 9 obtained an optimal bound, as follows.
Thomassen Reference 63 proved that a similar bound holds for $5$-colorable graphs embedded in a fixed surface.
In Reference 63, Theorem 2.1 Thomassen gave a short and elegant proof of Theorem 2.24. The argument also applies to $4$-colorings of triangle-free graphs and $3$-colorings of graphs of girth at least five. In Reference 64, Problem 2 Thomassen asked whether the bound of Theorem 2.23 holds for $5$-list-colorings and proved that a planar graph has exponentially many $5$-list-colorings.
In Theorem 3.22 we prove the weaker statement that the answer is yes if $c2^{|V(G)|}$ is replaced by $2^{c|V(G)|}$. This result was announced by Kawarabayashi and Mohar Reference 44, but no proof appeared so far.
Thomasssen Reference 65 also proved that planar graphs of girth at least five have exponentially many $3$-list-colorings.
In this section we formulate Theorem 3.8, our main coloring result, and derive a number of consequences from it.
We need to generalize rooted graphs to allow distinguished facial cycles, rather than just distinguished vertices. Hence the following definition.
Thus if $G$ is a graph with rings embedded in a surface $\Sigma$, then the rings are in one-to-one correspondence with the boundary components of $\Sigma$. In particular, if $G$ has no rings, then $\Sigma$ has no boundary.
Let us remark that this definition of a canvas is more general than the one we used in Reference 50 or Reference 51. We need the notion of a critical canvas, which we define as follows.
The above-defined families are the three most interesting families of canvases to which our theory applies. More generally, the theory applies to what we call good families of canvases. Those are defined in Definition 8.3, but for now we can treat this notion as a black box. We now state the fact that the families just defined are good. We prove it in Theorem 8.8, using results from other papers.
The following is our main coloring theorem.
Theorem 3.8 is an immediate consequence of Theorem 8.11, proved in Section 8, where it is deduced from Theorem 7.11. In the rest of this section we derive consequences of Theorem 3.8, some of which are new and some of which improve previous results. As a first consequence we improve the bound on $\gamma$ in Theorems 2.1 and 2.12, and extend Theorem 2.2 to list-coloring, while simultaneously improving upon the first and third outcome.
In fact, the proof shows the following strengthening.
The bound $\gamma (\log g+1)$ in Theorems 3.9 and 3.10 is asymptotically best possible, because by Reference 10, Theorem 4.1 there exist non-$5$-colorable graphs on $n$ vertices with girth $\Omega (\log n )$, and the Euler genus of a graph on $n$ vertices is obviously at most $n^2$.
The next consequence of Theorem 3.8 settles Conjecture 2.11, improves the bound on the size of $6$-critical graphs in Theorem 2.3, and extends Theorem 2.6 to list-critical graphs.
The bound in Theorem 3.11 is asymptotically best possible. For $5$-list-assignments it can be seen by considering the graphs obtained from copies of $K_6$ by applying Hajos’ construction. For $4$- and $3$-list-assignments we replace $K_6$ by a $5$-critical graph of girth four and a $4$-critical graph of girth five, respectively.
We have the following immediate corollary. If $k\ge 1$ is an integer, then we say that a graph $G$ is $k$-list-critical if $G$ is not $(k-1)$-list-colorable but every proper subgraph of $G$ is.
By the result of Eppstein Reference 31 mentioned earlier we have the following algorithmic consequence.
We can also deduce the following algorithm for $L$-coloring.
Let $G$ be a graph embedded in a surface $\Sigma$, and let $\Sigma '$ be the surface obtained by attaching a disk to every facial walk of the embedded graph $G$. Then $G$ is $2$-cell embedded in $\Sigma '$, and we say that the Euler genus of $\Sigma '$ is the combinatorial genus of the embedded graph $G$. We need the following well-known result. We include a proof for convenience.
Another consequence of Theorem 3.11 is the following, which gives an independent proof and extension of Theorem 2.13 (but with a worse constant).
The proof of Theorem 3.11 actually implies the following stronger form, which also generalizes Theorem 2.10 to $5$-list-coloring (albeit with $150$ replaced by a larger constant).
The next theorem implies the former Albertson’s conjecture (Theorem 2.18) and generalizes it to other surfaces, it generalizes Theorem 2.19 to list-coloring, it answers Question 2.20, and implies another result which we will discuss next. Let us remark that the difference between $G\left[V\left(\bigcup \mathcal{R}\right)\right]$ and $\mathcal{R}$ is that the former graph includes edges of $G$ with both ends in $\mathcal{R}$, including those that do not belong to $\mathcal{R}$.
The following theorem follows immediately from Theorem 3.19. The first assertion gives an independent proof of and generalizes Theorem 2.22.
We obtain the following generalization and independent proof of Theorem 2.21. For $5$-list-assignments it follows from Theorem 3.19 by replacing each crossing by a cycle of length four, but for the other two cases we need a more careful argument.
Finally we prove a weaker version of Problem 2.26. It is implied by the following more general theorem by setting $\mathcal{R}=\emptyset$.
4. Exponentially many colorings
The main result of this short section is Lemma 4.5, which strengthens Theorem 2.15 by saying that if an $L$-coloring of $C$ extends to $G$, then it has exponentially many extensions.
When Thomassen proved Theorem 2.25 in Reference 64, Theorem 4, he proved a stronger statement, which we state in a slightly stronger form.
We use Theorem 4.1 to deduce the following corollary.
Let us recall that $C$-critical graphs were defined in Definition 3.4. When we proved Theorem 2.15 in Reference 51, we have actually proven the following stronger result Reference 51, Theorem 6.1, which we will now need.
We are now ready to prove the main result of this section.
5. Definition and examples of hyperbolic families
In this section we define hyperbolic families in full generality and we give examples of families of embedded graphs with rings that are hyperbolic. Let us recall that embedded graphs with rings were defined at the beginning of Section 3.
The next lemma shows that if a planar graph with rings belongs to a hyperbolic family, then it has at least one ring.
5.1. Examples arising from (list-)coloring
Theorem 2.15 implies that embedded $6$-list-critical graphs form a hyperbolic family. To obtain a better bound on the Cheeger constant we actually use the stronger Theorem 4.4. More generally, we have the following.
For our next example, we need the following lemma. The degree of a vertex $v$ in a graph $G$ will be denoted by $\deg _G(v)$, or $\deg (v)$ if the graph is understood from the context.
For our next example, we need the following lemma. The size of a face $f$ of an embedded graph, denoted by $|f|$, is the sum of the lengths of the walks bounding $f$.
For our next example, we need the following lemma.
A $k$-coloring$\phi$ of a graph $G$ is acyclic if every two color classes induce an acyclic graph. Borodin Reference 12 proved that every planar graph has an acyclic $5$-coloring.
Our next example is related to the following conjecture of Steinberg from 1976 Reference 42, Problem 2.9.
While Steinberg’s conjecture was recently disproved by Cohen-Addad, Hebdige, Král’, Li, and Salgado Reference 15, Borodin, Glebov, Montassier, and Raspaud Reference 13 showed that every planar graph with no cycles of length four, five, six, or seven is $3$-colorable. That leads us to the following example.
5.2. Examples pertaining to exponentially many colorings
The following lemma follows from the work of Kelly and Postle Reference 46.
6. The structure of hyperbolic families
In this section we investigate the structure of hyperbolic families of embedded graphs with rings. The main result is Theorem 6.28. We progress to the main result as follows. In Subsection 6.1, we define “frames”, which are essentially a subgraph of an embedded graph with only one face. We also show that every $2$-cell-embedded graph has a frame (Lemma 6.2) and that minimal frames satisfy certain geodesic properties (Lemma 6.6). In Subsection 6.2 we show (Lemma 6.10) that for hyperbolic families the vertices in the interior of a disk have “logarithmic distance” to the boundary of the disk (an improvement over the trivial bound of linear distance as guaranteed by the definition of hyperbolic). Conversely, then, the neighborhood of a vertex contained in a disk experiences “exponential growth” in its diameter (Lemma 6.13).
Combining these ideas in Subsection 6.3, we prove the key Theorem 6.20, which says that large hyperbolic graphs have a short (i.e., as a function of the Cheeger constant) non-null homotopic cycle. Theorem 6.20 is the key to proving the main result, Theorem 6.28. The intuition for the proof of Theorem 6.20 is that if no such cycle exists, then balls around the midpoints of the segments of the frame have exponential growth in the lengths of the segments, while by hyperbolicity, the whole graph is linear in the size of the frame which is equal to the sum of the lengths of its segments. This linear upped bound versus the exponential growth then provides a contradiction.
Finally in Subsection 6.4, we prove the main result (Theorem 6.28), which provides a structural decomposition for hyperbolic families by asserting that all but $O(g)$ vertices of a graph in such a family belong to cylinders of small edge-width (which we call “sleeves”). The proof of Theorem 6.28 proceeds inductively by cutting along the short cycles guaranteed by Theorem 6.20.
6.1. Frames
Our next lemma shows that the number of non-ring segments of a frame is bounded by a function of the Euler genus and the number of rings.
6.2. Separations and growth rates
If $G$ belongs to a hyperbolic family, then, as we show next, the same linear bound holds for closed curves that bound “pinched” disks, or, equivalently, it holds for flat separations. But first we need the following lemma, which says that a flat separation is determined by the faces of a certain multigraph.
We are now ready to prove that if $G$ belongs to a hyperbolic family, then the same linear bound holds for closed curves that bound “pinched” disks, or, equivalently, it holds for flat separations.
The next lemma says that every vertex on the “flat” side of a flat separation is at most logarithmic distance away from the middle part of the separation.
Next we will show that planar neighborhoods in a hyperbolic family exhibit exponential growth, but first we need the following lemma. The lemma formalizes the fact that if a vertex $v$ is not near a short non-null-homotopic cycle, then the vertices up to a certain distance from $v$ form a planar graph, indeed they lie inside a disk.
We now show that planar neighborhoods in a hyperbolic family exhibit exponential growth.
6.3. Edge-width of hyperbolic families
The next lemma says that every vertex that is at least logarithmic distance away from every ring is contained in a non-null-homotopic cycle of at most logarithmic length.
Let us recall that if $\Sigma$ is a surface with boundary, then $\widehat{\Sigma }$ denotes the surface without boundary obtained by gluing a disk to each component of the boundary.
If $G$ is a graph with no rings embedded in a surface, then its edge-width is usually defined as the maximum integer $k$ such that every non-null-homotopic cycle in $G$ has length at least $k$. We extend this definition to graphs with rings as follows.
Our next lemma says that if an embedded graph with rings belonging to a hyperbolic family is embedded with moderately large edge-width (logarithmic in the number of vertices), then it has a specific structure. First we define the structure.
Let us remark that if $G$ is locally cylindrical, then each component of $G$ may be regarded as a graph with one ring embedded in a disk, and if this embedded graph belongs to the hyperbolic family $\mathcal{F}$, then its number of vertices is bounded by a linear function of the length of the ring by Lemma 5.2.
In what follows we will need the embedded graph to be $2$-cell embedded. If it is not, then there is an obvious way to simplify the surface, but we need to know that the new embedded graph belongs to the same family. Hence the following definition.
In the next example we exhibit a hyperbolic family such that the family obtained from it by curve cutting is not hyperbolic.
The next theorem improves upon the length of the non-null-homotopic cycle guaranteed by Lemma 6.14 from logarithmic to constant, assuming the graph is not too small. The theorem will be a key tool in proving Theorem 6.28, the main result of this section.
The following corollary is an upgrade of Lemma 6.17.
Our motivation for the study of hyperbolic families is to understand graphs that contain no subgraph isomorphic to a member of the family. The following is the first of several results along those lines. It is a more precise version of Theorem 1.2.
6.4. Structure of hyperbolic families
Our objective is to prove Theorem 6.28, but first we need the following notion.
It should be noted that despite the similarity in names, curve cutting and cycle cutting play different roles: while the next lemma shows that closure under cycle cutting can be obtained for free, Example 6.19 shows that that is not the case for curve cutting. On the other hand, all hyperbolic families of embedded graphs of interest to us are indeed closed under curve cutting, and hence we make that assumption whenever it is convenient to do so.
In the next two definitions we formalize the concept of narrow cylinder and a graph being decomposed into a bounded size graph and narrow cylinders.
The following is an easy bound on the number of sleeves in a sleeve-decomposition.
We are ready to prove the main result of this section. It states that a graph in a hyperbolic family has a sleeve-decomposition with parameters $(k,l,m)$, where $k,l,m$ depend only on the Euler genus $g$, the total number of ring vertices $R$, and the Cheeger constant $c$. Moreover, the number of sleeves is also bounded.
By using induction when $\Sigma$ is not connected we obtain the following easier-to-state bound.
We deduce the following consequence in the spirit of Theorems 2.13 and 3.17, but we need a definition first.
6.5. From local freedom to global freedom
In this section we prove a generalization of Corollary 6.22.
The following is a generalization of Corollary 6.22 to graphs with rings.
7. Strongly hyperbolic families
Let $\mathcal{F}$ be a hyperbolic family of embedded graphs, and let $\Sigma$ and $R$ be fixed. Are there arbitrarily large members of $\mathcal{F}$ that are embedded in $\Sigma$ with a total of $R$ ring vertices? Theorem 6.28 implies that the answer depends on whether there exist arbitrarily large sleeves. That motivates the following definition.
We can now answer the question posed at the beginning of this section.
In the definition of strong hyperbolicity we imposed a constant bound on the number of vertices in cylinders with boundary components of bounded length. As the next theorem shows, it follows that this implies a linear bound for cylinders with boundaries of any length.
7.1. Examples
The following theorem is proved in Reference 48. The proof is long and its journal version will be split into multiple papers, the first three of which are Reference 50Reference 51Reference 52.
The analog of Theorem 7.4 for graphs of girth five and $3$-list-assignments is shown in Reference 49, Theorem 1.8.
We deduce the following lemma.
Let us point out a subtlety: the family of Lemma 7.8 is a proper subfamily of the family of Lemma 5.13. In fact, the latter family is not strongly hyperbolic.
The strong hyperbolicity of the family in the next example follows from Theorem 8.8.
7.2. The structure of strongly hyperbolic families
Let us recall that the combinatorial genus of an embedded graph was defined prior to Lemma 3.16. The following is our main result about strongly hyperbolic families of embedded graphs.
Theorem 7.11 has the following variation, where we eliminate outcome (d) at the expense of increasing the value of $l_C$.
8. Canvases
In this section we prove Theorem 3.8. It is an immediate consequence of Theorem 8.11. Let us recall that canvases and critical canvases were defined in Definition 3.3.
To prove that certain families of canvases are good we need a lemma. To state the lemma we need to consider the following properties of families of canvases.
The lemma we need is the following.
Let us recall that the families $\mathcal{C}_3,\mathcal{C}_4$, and $\mathcal{C}_5$ were defined in Definition 3.5. In order to apply Lemma 8.6 we need to show that these families satisfy properties (P1) and (P2).
In the next theorem we show that if a coloring of the rings extends for a canvas in a critically exponentially hyperbolic family, then it has exponentially many extensions.
The following is our main result about good families of canvases.
We can consolidate outcomes (b)-(d) of the previous theorem to obtain the following simpler version, which implies Theorem 3.8.
By applying Theorem 7.12 instead of Theorem 7.11 we obtain the following variation of Theorem 8.10. We omit the almost identical proof.
Acknowledgment
This paper is based on part of the doctoral dissertation Reference 48 of the first author, written under the guidance of the second author.
V. A. Aksenov, The extension of a $3$-coloring on planar graphs(Russian), Diskret. Analiz Vyp. 26 Grafy i Testy (1974), 3–19, 84. MR0543788, Show rawAMSref\bib{Aks}{article}{
author={Aksenov, V. A.},
title={The extension of a $3$-coloring on planar graphs},
language={Russian},
journal={Diskret. Analiz Vyp. 26 Grafy i Testy},
date={1974},
pages={3--19, 84},
review={\MR {0543788}},
}
Reference [2]
Michael O. Albertson, You can’t paint yourself into a corner, J. Combin. Theory Ser. B 73 (1998), no. 2, 189–194, DOI 10.1006/jctb.1998.1827. MR1632011, Show rawAMSref\bib{Alb}{article}{
author={Albertson, Michael O.},
title={You can't paint yourself into a corner},
journal={J. Combin. Theory Ser. B},
volume={73},
date={1998},
number={2},
pages={189--194},
issn={0095-8956},
review={\MR {1632011}},
doi={10.1006/jctb.1998.1827},
}
Reference [3]
Michael O. Albertson and Joan P. Hutchinson, The three excluded cases of Dirac’s map-color theorem, Second International Conference on Combinatorial Mathematics (New York, 1978), Ann. New York Acad. Sci., vol. 319, New York Acad. Sci., New York, 1979, pp. 7–17. MR556001, Show rawAMSref\bib{AlbHutch1}{article}{
author={Albertson, Michael O.},
author={Hutchinson, Joan P.},
title={The three excluded cases of Dirac's map-color theorem},
conference={ title={Second International Conference on Combinatorial Mathematics (New York, 1978)}, },
book={ series={Ann. New York Acad. Sci.}, volume={319}, publisher={New York Acad. Sci., New York}, },
date={1979},
pages={7--17},
review={\MR {556001}},
}
Reference [4]
Michael O. Albertson and Joan P. Hutchinson, Extending colorings of locally planar graphs, J. Graph Theory 36 (2001), no. 2, 105–116, DOI 10.1002/1097-0118(200102)36:2<105::AID-JGT5>3.3.CO;2-8. MR1805498, Show rawAMSref\bib{AlbHutch2}{article}{
author={Albertson, Michael O.},
author={Hutchinson, Joan P.},
title={Extending colorings of locally planar graphs},
journal={J. Graph Theory},
volume={36},
date={2001},
number={2},
pages={105--116},
issn={0364-9024},
review={\MR {1805498}},
doi={10.1002/1097-0118(200102)36:2<105::AID-JGT5>3.3.CO;2-8},
}
[5]
Michael O. Albertson and Joan P. Hutchinson, Graph color extensions: when Hadwiger’s conjecture and embeddings help, Electron. J. Combin. 9 (2002), no. 1, Research Paper 37, 10. MR1928789, Show rawAMSref\bib{AlbHutch3}{article}{
author={Albertson, Michael O.},
author={Hutchinson, Joan P.},
title={Graph color extensions: when Hadwiger's conjecture and embeddings help},
journal={Electron. J. Combin.},
volume={9},
date={2002},
number={1},
pages={Research Paper 37, 10},
issn={1077-8926},
review={\MR {1928789}},
}
[6]
Michael O. Albertson and Joan P. Hutchinson, Extending precolorings of subgraphs of locally planar graphs, European J. Combin. 25 (2004), no. 6, 863–871, DOI 10.1016/j.ejc.2003.06.005. MR2079903, Show rawAMSref\bib{AlbHutch4}{article}{
author={Albertson, Michael O.},
author={Hutchinson, Joan P.},
title={Extending precolorings of subgraphs of locally planar graphs},
journal={European J. Combin.},
volume={25},
date={2004},
number={6},
pages={863--871},
issn={0195-6698},
review={\MR {2079903}},
doi={10.1016/j.ejc.2003.06.005},
}
Reference [7]
K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR0543792, Show rawAMSref\bib{4CT1}{article}{
author={Appel, K.},
author={Haken, W.},
title={Every planar map is four colorable. I. Discharging},
journal={Illinois J. Math.},
volume={21},
date={1977},
number={3},
pages={429--490},
issn={0019-2082},
review={\MR {0543792}},
}
Reference [8]
K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977), no. 3, 491–567. MR0543793, Show rawAMSref\bib{4CT2}{article}{
author={Appel, K.},
author={Haken, W.},
author={Koch, J.},
title={Every planar map is four colorable. II. Reducibility},
journal={Illinois J. Math.},
volume={21},
date={1977},
number={3},
pages={491--567},
issn={0019-2082},
review={\MR {0543793}},
}
Reference [9]
G. D. Birkhoff and D. C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), 355–451, DOI 10.2307/1990348. MR0018401, Show rawAMSref\bib{BirLew}{article}{
author={Birkhoff, G. D.},
author={Lewis, D. C.},
title={Chromatic polynomials},
journal={Trans. Amer. Math. Soc.},
volume={60},
date={1946},
pages={355--451},
issn={0002-9947},
review={\MR {0018401}},
doi={10.2307/1990348},
}
Reference [10]
Béla Bollobás, Extremal graph theory, London Mathematical Society Monographs, vol. 11, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR506522, Show rawAMSref\bib{BolExtremal}{book}{
author={Bollob\'as, B\'ela},
title={Extremal graph theory},
series={London Mathematical Society Monographs},
volume={11},
publisher={Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York},
date={1978},
pages={xx+488},
isbn={0-12-111750-2},
review={\MR {506522}},
}
Reference [11]
Béla Bollobás, Modern graph theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998, DOI 10.1007/978-1-4612-0619-4. MR1633290, Show rawAMSref\bib{Bollobas}{book}{
author={Bollob\'as, B\'ela},
title={Modern graph theory},
series={Graduate Texts in Mathematics},
volume={184},
publisher={Springer-Verlag, New York},
date={1998},
pages={xiv+394},
isbn={0-387-98488-7},
review={\MR {1633290}},
doi={10.1007/978-1-4612-0619-4},
}
Reference [12]
O. V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979), no. 3, 211–236, DOI 10.1016/0012-365X(79)90077-3. MR534939, Show rawAMSref\bib{Borodin}{article}{
author={Borodin, O. V.},
title={On acyclic colorings of planar graphs},
journal={Discrete Math.},
volume={25},
date={1979},
number={3},
pages={211--236},
issn={0012-365X},
review={\MR {534939}},
doi={10.1016/0012-365X(79)90077-3},
}
Reference [13]
O. V. Borodin, A. N. Glebov, M. Montassier, and A. Raspaud, Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable, J. Combin. Theory Ser. B 99 (2009), no. 4, 668–673, DOI 10.1016/j.jctb.2008.11.001. MR2518199, Show rawAMSref\bib{BorGleMonRas}{article}{
author={Borodin, O. V.},
author={Glebov, A. N.},
author={Montassier, M.},
author={Raspaud, A.},
title={Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable},
journal={J. Combin. Theory Ser. B},
volume={99},
date={2009},
number={4},
pages={668--673},
issn={0095-8956},
review={\MR {2518199}},
doi={10.1016/j.jctb.2008.11.001},
}
Reference [14]
Nathan Chenette, Luke Postle, Noah Streib, Robin Thomas, and Carl Yerger, Five-coloring graphs on the Klein bottle, J. Combin. Theory Ser. B 102 (2012), no. 5, 1067–1098, DOI 10.1016/j.jctb.2012.05.001. MR2959391, Show rawAMSref\bib{KB}{article}{
author={Chenette, Nathan},
author={Postle, Luke},
author={Streib, Noah},
author={Thomas, Robin},
author={Yerger, Carl},
title={Five-coloring graphs on the Klein bottle},
journal={J. Combin. Theory Ser. B},
volume={102},
date={2012},
number={5},
pages={1067--1098},
issn={0095-8956},
review={\MR {2959391}},
doi={10.1016/j.jctb.2012.05.001},
}
Reference [15]
Vincent Cohen-Addad, Michael Hebdige, Daniel Král’, Zhentao Li, and Esteban Salgado, Steinberg’s conjecture is false, J. Combin. Theory Ser. B 122 (2017), 452–456, DOI 10.1016/j.jctb.2016.07.006. MR3575214, Show rawAMSref\bib{CohHebKraLiSal}{article}{
author={Cohen-Addad, Vincent},
author={Hebdige, Michael},
author={Kr\'al', Daniel},
author={Li, Zhentao},
author={Salgado, Esteban},
title={Steinberg's conjecture is false},
journal={J. Combin. Theory Ser. B},
volume={122},
date={2017},
pages={452--456},
issn={0095-8956},
review={\MR {3575214}},
doi={10.1016/j.jctb.2016.07.006},
}
Reference [16]
Alice M. Dean and Joan P. Hutchinson, List-coloring graphs on surfaces with varying list-sizes, Electron. J. Combin. 19 (2012), no. 4, Paper 50, 16. MR3007185, Show rawAMSref\bib{DeanHutch}{article}{
author={Dean, Alice M.},
author={Hutchinson, Joan P.},
title={List-coloring graphs on surfaces with varying list-sizes},
journal={Electron. J. Combin.},
volume={19},
date={2012},
number={4},
pages={Paper 50, 16},
issn={1077-8926},
review={\MR {3007185}},
}
Reference [17]
Matt DeVos, Ken-ichi Kawarabayashi, and Bojan Mohar, Locally planar graphs are 5-choosable, J. Combin. Theory Ser. B 98 (2008), no. 6, 1215–1232, DOI 10.1016/j.jctb.2008.01.003. MR2462315, Show rawAMSref\bib{DeVos}{article}{
author={DeVos, Matt},
author={Kawarabayashi, Ken-ichi},
author={Mohar, Bojan},
title={Locally planar graphs are 5-choosable},
journal={J. Combin. Theory Ser. B},
volume={98},
date={2008},
number={6},
pages={1215--1232},
issn={0095-8956},
review={\MR {2462315}},
doi={10.1016/j.jctb.2008.01.003},
}
Reference [18]
Reinhard Diestel, Graph theory, 4th ed., Graduate Texts in Mathematics, vol. 173, Springer, Heidelberg, 2010, DOI 10.1007/978-3-642-14279-6. MR2744811, Show rawAMSref\bib{Diestel}{book}{
author={Diestel, Reinhard},
title={Graph theory},
series={Graduate Texts in Mathematics},
volume={173},
edition={4},
publisher={Springer, Heidelberg},
date={2010},
pages={xviii+437},
isbn={978-3-642-14278-9},
review={\MR {2744811}},
doi={10.1007/978-3-642-14279-6},
}
Reference [19]
G. A. Dirac, Map-colour theorems, Canadian J. Math. 4 (1952), 480–490. MR0050869, Show rawAMSref\bib{Dirac1}{article}{
author={Dirac, G. A.},
title={Map-colour theorems},
journal={Canadian J. Math.},
volume={4},
date={1952},
pages={480--490},
issn={0008-414X},
review={\MR {0050869}},
}
Reference [20]
G. A. Dirac, The colouring of maps, J. London Math. Soc. 28 (1953), 476–480, DOI 10.1112/jlms/s1-28.4.476. MR0056904, Show rawAMSref\bib{Dirac2}{article}{
author={Dirac, G. A.},
title={The colouring of maps},
journal={J. London Math. Soc.},
volume={28},
date={1953},
pages={476--480},
issn={0024-6107},
review={\MR {0056904}},
doi={10.1112/jlms/s1-28.4.476},
}
Reference [21]
Zdeněk Dvořák, 3-choosability of planar graphs with $(\leq 4)$-cycles far apart, J. Combin. Theory Ser. B 104 (2014), 28–59, DOI 10.1016/j.jctb.2013.10.004. MR3132743, Show rawAMSref\bib{3ChooseFarApart}{article}{
author={Dvo\v r\'ak, Zden\v ek},
title={3-choosability of planar graphs with $(\leq 4)$-cycles far apart},
journal={J. Combin. Theory Ser. B},
volume={104},
date={2014},
pages={28--59},
issn={0095-8956},
review={\MR {3132743}},
doi={10.1016/j.jctb.2013.10.004},
}
Reference [22]
Zdeněk Dvořák and Ken-ichi Kawarabayashi, Choosability of planar graphs of girth $5$, arXiv:1109.2976v1.
[23]
Zdeněk Dvořák and Ken-ichi Kawarabayashi, List-coloring embedded graphs, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2012, pp. 1004–1012. MR3202964, Show rawAMSref\bib{DvoKawListEmb}{article}{
author={Dvo\v r\'ak, Zden\v ek},
author={Kawarabayashi, Ken-ichi},
title={List-coloring embedded graphs},
conference={ title={Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms}, },
book={ publisher={SIAM, Philadelphia, PA}, },
date={2012},
pages={1004--1012},
review={\MR {3202964}},
}
Reference [24]
Zdeněk Dvořák, Daniel Král’, and Robin Thomas, Three-coloring triangle-free graphs on surfaces, Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New York, NY (2009), 120–129.
Reference [25]
Zdeněk Dvořák, Daniel Král’, and Robin Thomas, Testing first-order properties for subclasses of sparse graphs, J. ACM 60 (2013), no. 5, Art. 36, 24, DOI 10.1145/2499483. MR3124685, Show rawAMSref\bib{DvoKraThofol}{article}{
author={Dvo\v r\'ak, Zden\v ek},
author={Kr\'al', Daniel},
author={Thomas, Robin},
title={Testing first-order properties for subclasses of sparse graphs},
journal={J. ACM},
volume={60},
date={2013},
number={5},
pages={Art. 36, 24},
issn={0004-5411},
review={\MR {3124685}},
doi={10.1145/2499483},
}
Reference [26]
Zdeněk Dvořák, Daniel Král’, and Robin Thomas, Three-coloring triangle-free graphs on surfaces III. Graphs of girth five, arXiv:1402.4710.
Reference [27]
Zdeněk Dvořák, Daniel Král’, and Robin Thomas, Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies, arXiv:0911.0885.
Reference [28]
Zdeněk Dvořák, Daniel Král’, and Robin Thomas, Three-coloring triangle-free graphs on surfaces VI. $3$-colorability of quadrangulations, arXiv:1509.01013.
Reference [29]
Zdeněk Dvořák, Bernard Lidický, and Bojan Mohar, 5-choosability of graphs with crossings far apart, J. Combin. Theory Ser. B 123 (2017), 54–96, DOI 10.1016/j.jctb.2016.11.004. MR3597095, Show rawAMSref\bib{Crossings}{article}{
author={Dvo\v r\'ak, Zden\v ek},
author={Lidick\'y, Bernard},
author={Mohar, Bojan},
title={5-choosability of graphs with crossings far apart},
journal={J. Combin. Theory Ser. B},
volume={123},
date={2017},
pages={54--96},
issn={0095-8956},
review={\MR {3597095}},
doi={10.1016/j.jctb.2016.11.004},
}
Reference [30]
Zdeněk Dvořák, Bernard Lidický, Bojan Mohar, and Luke Postle, 5-list-coloring planar graphs with distant precolored vertices, J. Combin. Theory Ser. B 122 (2017), 311–352, DOI 10.1016/j.jctb.2016.06.006. MR3575207, Show rawAMSref\bib{AlbertsonsConj}{article}{
author={Dvo\v r\'ak, Zden\v ek},
author={Lidick\'y, Bernard},
author={Mohar, Bojan},
author={Postle, Luke},
title={5-list-coloring planar graphs with distant precolored vertices},
journal={J. Combin. Theory Ser. B},
volume={122},
date={2017},
pages={311--352},
issn={0095-8956},
review={\MR {3575207}},
doi={10.1016/j.jctb.2016.06.006},
}
Reference [31]
David Eppstein, Subgraph isomorphism in planar graphs and related problems, J. Graph Algorithms Appl. 3 (1999), no. 3, 27, DOI 10.7155/jgaa.00014. MR1750082, Show rawAMSref\bib{Eppstein2}{article}{
author={Eppstein, David},
title={Subgraph isomorphism in planar graphs and related problems},
journal={J. Graph Algorithms Appl.},
volume={3},
date={1999},
pages={no. 3, 27},
issn={1526-1719},
review={\MR {1750082}},
doi={10.7155/jgaa.00014},
}
Reference [32]
Paul Erdős, Arthur L. Rubin, and Herbert Taylor, Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer., XXVI, Utilitas Math., Winnipeg, Man., 1980, pp. 125–157. MR593902, Show rawAMSref\bib{ErdRubTay}{article}{
author={Erd\H os, Paul},
author={Rubin, Arthur L.},
author={Taylor, Herbert},
title={Choosability in graphs},
conference={ title={Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing}, address={Humboldt State Univ., Arcata, Calif.}, date={1979}, },
book={ series={Congress. Numer., XXVI}, publisher={Utilitas Math., Winnipeg, Man.}, },
date={1980},
pages={125--157},
review={\MR {593902}},
}
Reference [33]
P. Franklin, A Six Color Problem, J. Math. Phys. 13 (1934), 363–379.
Reference [34]
Steve Fisk, The nonexistence of colorings, J. Combinatorial Theory Ser. B 24 (1978), no. 2, 247–248. MR0491299, Show rawAMSref\bib{Fisk}{article}{
author={Fisk, Steve},
title={The nonexistence of colorings},
journal={J. Combinatorial Theory Ser. B},
volume={24},
date={1978},
number={2},
pages={247--248},
review={\MR {0491299}},
}
Reference [35]
Steve Fisk and Bojan Mohar, Coloring graphs without short nonbounding cycles, J. Combin. Theory Ser. B 60 (1994), no. 2, 268–276, DOI 10.1006/jctb.1994.1018. MR1271274, Show rawAMSref\bib{FisMoh}{article}{
author={Fisk, Steve},
author={Mohar, Bojan},
title={Coloring graphs without short nonbounding cycles},
journal={J. Combin. Theory Ser. B},
volume={60},
date={1994},
number={2},
pages={268--276},
issn={0095-8956},
review={\MR {1271274}},
doi={10.1006/jctb.1994.1018},
}
Reference [36]
T. Gallai, Kritische Graphen. II(German, with Russian summary), Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963), 373–395 (1964). MR0188100, Show rawAMSref\bib{Gallai}{article}{
author={Gallai, T.},
title={Kritische Graphen. II},
language={German, with Russian summary},
journal={Magyar Tud. Akad. Mat. Kutat\'o Int. K\"ozl.},
volume={8},
date={1963},
pages={373--395 (1964)},
review={\MR {0188100}},
}
Reference [37]
Michael R. Garey and David S. Johnson, Computers and intractability, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness; A Series of Books in the Mathematical Sciences. MR519066, Show rawAMSref\bib{GarJoh}{book}{
author={Garey, Michael R.},
author={Johnson, David S.},
title={Computers and intractability},
note={A guide to the theory of NP-completeness; A Series of Books in the Mathematical Sciences},
publisher={W. H. Freeman and Co., San Francisco, Calif.},
date={1979},
pages={x+338},
isbn={0-7167-1045-5},
review={\MR {519066}},
}
[38]
John Gimbel and Carsten Thomassen, Coloring graphs with fixed genus and girth, Trans. Amer. Math. Soc. 349 (1997), no. 11, 4555–4564, DOI 10.1090/S0002-9947-97-01926-0. MR1422897, Show rawAMSref\bib{GimbelThom}{article}{
author={Gimbel, John},
author={Thomassen, Carsten},
title={Coloring graphs with fixed genus and girth},
journal={Trans. Amer. Math. Soc.},
volume={349},
date={1997},
number={11},
pages={4555--4564},
issn={0002-9947},
review={\MR {1422897}},
doi={10.1090/S0002-9947-97-01926-0},
}
Reference [39]
Herbert Grötzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel(German), Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 8 (1958/1959), 109–120. MR0116320, Show rawAMSref\bib{Gro}{article}{
author={Gr\"otzsch, Herbert},
title={Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz f\"ur dreikreisfreie Netze auf der Kugel},
language={German},
journal={Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe},
volume={8},
date={1958/1959},
pages={109--120},
review={\MR {0116320}},
}
Reference [40]
Ivan Havel, O zbarvitelnosti rovinných grafů třemi barvami, Mathematics (Geometry and Graph Theory), Univ. Karlova, Prague (1970), 89–91.
[41]
Joan P. Hutchinson, On list-coloring extendable outerplanar graphs, Ars Math. Contemp. 5 (2012), no. 1, 171–184. MR2880673, Show rawAMSref\bib{HutchOuterplanar}{article}{
author={Hutchinson, Joan P.},
title={On list-coloring extendable outerplanar graphs},
journal={Ars Math. Contemp.},
volume={5},
date={2012},
number={1},
pages={171--184},
issn={1855-3966},
review={\MR {2880673}},
}
Reference [42]
T. R. Jensen and B. Toft, Graph Coloring Problems, J. Wiley & Sons, New York, Chichester, Brisbane, Toronto, Singapore 1995.
Reference [43]
Ken-ichi Kawarabayashi, Daniel Kráľ, Jan Kynčl, and Bernard Lidický, 6-critical graphs on the Klein bottle, SIAM J. Discrete Math. 23 (2008/09), no. 1, 372–383, DOI 10.1137/070706835. MR2476836, Show rawAMSref\bib{KB2}{article}{
author={Kawarabayashi, Ken-ichi},
author={Kr\'a\v l, Daniel},
author={Kyn\v cl, Jan},
author={Lidick\'y, Bernard},
title={6-critical graphs on the Klein bottle},
journal={SIAM J. Discrete Math.},
volume={23},
date={2008/09},
number={1},
pages={372--383},
issn={0895-4801},
review={\MR {2476836}},
doi={10.1137/070706835},
}
Reference [44]
Ken-ichi Kawarabayashi and Bojan Mohar, List-color-critical graphs on a fixed surface, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2009, pp. 1156–1165. MR2807558, Show rawAMSref\bib{KM}{article}{
author={Kawarabayashi, Ken-ichi},
author={Mohar, Bojan},
title={List-color-critical graphs on a fixed surface},
conference={ title={Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms}, },
book={ publisher={SIAM, Philadelphia, PA}, },
date={2009},
pages={1156--1165},
review={\MR {2807558}},
}
Reference [45]
Ken-ichi Kawarabayashi and Carsten Thomassen, From the plane to higher surfaces, J. Combin. Theory Ser. B 102 (2012), no. 4, 852–868, DOI 10.1016/j.jctb.2012.03.001. MR2927410, Show rawAMSref\bib{KawThofrom}{article}{
author={Kawarabayashi, Ken-ichi},
author={Thomassen, Carsten},
title={From the plane to higher surfaces},
journal={J. Combin. Theory Ser. B},
volume={102},
date={2012},
number={4},
pages={852--868},
issn={0095-8956},
review={\MR {2927410}},
doi={10.1016/j.jctb.2012.03.001},
}
Reference [46]
Tom Kelly and Luke Postle, Exponentially many 4-list colorings of triangle-free graphs on surfaces, J. Graph Theory 87 (2018), no. 2, 230–238, DOI 10.1002/jgt.22153. MR3742180, Show rawAMSref\bib{KelPos}{article}{
author={Kelly, Tom},
author={Postle, Luke},
title={Exponentially many 4-list colorings of triangle-free graphs on surfaces},
journal={J. Graph Theory},
volume={87},
date={2018},
number={2},
pages={230--238},
issn={0364-9024},
review={\MR {3742180}},
doi={10.1002/jgt.22153},
}
[47]
Bojan Mohar and Carsten Thomassen, Graphs on surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001. MR1844449, Show rawAMSref\bib{MoharThom}{book}{
author={Mohar, Bojan},
author={Thomassen, Carsten},
title={Graphs on surfaces},
series={Johns Hopkins Studies in the Mathematical Sciences},
publisher={Johns Hopkins University Press, Baltimore, MD},
date={2001},
pages={xii+291},
isbn={0-8018-6689-8},
review={\MR {1844449}},
}
Reference [48]
Luke Jamison Postle, 5-list-coloring graphs on surfaces, ProQuest LLC, Ann Arbor, MI, 2012. Thesis (Ph.D.)–Georgia Institute of Technology. MR3152411, Show rawAMSref\bib{PosPhD}{book}{
author={Postle, Luke Jamison},
title={5-list-coloring graphs on surfaces},
note={Thesis (Ph.D.)--Georgia Institute of Technology},
publisher={ProQuest LLC, Ann Arbor, MI},
date={2012},
pages={253},
isbn={978-1267-89709-1},
review={\MR {3152411}},
}
Reference [49]
Luke Postle, 3 list coloring graphs of girth at least five on surfaces, arXiv:1710.06898v1.
Reference [50]
Luke Postle and Robin Thomas, Five-list-coloring graphs on surfaces I. Two lists of size two in planar graphs, J. Combin. Theory Ser. B 111 (2015), 234–241, DOI 10.1016/j.jctb.2014.08.003. MR3315607, Show rawAMSref\bib{PosThoTwotwo}{article}{
author={Postle, Luke},
author={Thomas, Robin},
title={Five-list-coloring graphs on surfaces I. Two lists of size two in planar graphs},
journal={J. Combin. Theory Ser. B},
volume={111},
date={2015},
pages={234--241},
issn={0095-8956},
review={\MR {3315607}},
doi={10.1016/j.jctb.2014.08.003},
}
Reference [51]
Luke Postle and Robin Thomas, Five-list-coloring graphs on surfaces II. A linear bound for critical graphs in a disk, J. Combin. Theory Ser. B 119 (2016), 42–65, DOI 10.1016/j.jctb.2015.12.005. MR3486337, Show rawAMSref\bib{PosThoLinDisk}{article}{
author={Postle, Luke},
author={Thomas, Robin},
title={Five-list-coloring graphs on surfaces II. A linear bound for critical graphs in a disk},
journal={J. Combin. Theory Ser. B},
volume={119},
date={2016},
pages={42--65},
issn={0095-8956},
review={\MR {3486337}},
doi={10.1016/j.jctb.2015.12.005},
}
Reference [52]
Luke Postle and Robin Thomas, Five-list-coloring graphs on surfaces III. One list of size one and one list of size two, J. Combin. Theory Ser. B 128 (2018), 1–16, DOI 10.1016/j.jctb.2017.06.004. MR3725183, Show rawAMSref\bib{PosThoTwoOne}{article}{
author={Postle, Luke},
author={Thomas, Robin},
title={Five-list-coloring graphs on surfaces III. One list of size one and one list of size two},
journal={J. Combin. Theory Ser. B},
volume={128},
date={2018},
pages={1--16},
issn={0095-8956},
review={\MR {3725183}},
doi={10.1016/j.jctb.2017.06.004},
}
Reference [53]
Gerhard Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U.S.A. 60 (1968), 438–445. MR0228378, Show rawAMSref\bib{RingelYoungs}{article}{
author={Ringel, Gerhard},
author={Youngs, J. W. T.},
title={Solution of the Heawood map-coloring problem},
journal={Proc. Nat. Acad. Sci. U.S.A.},
volume={60},
date={1968},
pages={438--445},
issn={0027-8424},
review={\MR {0228378}},
}
Reference [54]
Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997), no. 1, 2–44, DOI 10.1006/jctb.1997.1750. MR1441258, Show rawAMSref\bib{4CTRSST}{article}{
author={Robertson, Neil},
author={Sanders, Daniel},
author={Seymour, Paul},
author={Thomas, Robin},
title={The four-colour theorem},
journal={J. Combin. Theory Ser. B},
volume={70},
date={1997},
number={1},
pages={2--44},
issn={0095-8956},
review={\MR {1441258}},
doi={10.1006/jctb.1997.1750},
}
Reference [55]
Carsten Thomassen, Five-coloring maps on surfaces, J. Combin. Theory Ser. B 59 (1993), no. 1, 89–105, DOI 10.1006/jctb.1993.1057. MR1234386, Show rawAMSref\bib{Tho5colmaps}{article}{
author={Thomassen, Carsten},
title={Five-coloring maps on surfaces},
journal={J. Combin. Theory Ser. B},
volume={59},
date={1993},
number={1},
pages={89--105},
issn={0095-8956},
review={\MR {1234386}},
doi={10.1006/jctb.1993.1057},
}
Reference [56]
Carsten Thomassen, Five-coloring graphs on the torus, J. Combin. Theory Ser. B 62 (1994), no. 1, 11–33, DOI 10.1006/jctb.1994.1052. MR1290628, Show rawAMSref\bib{ThomTorus}{article}{
author={Thomassen, Carsten},
title={Five-coloring graphs on the torus},
journal={J. Combin. Theory Ser. B},
volume={62},
date={1994},
number={1},
pages={11--33},
issn={0095-8956},
review={\MR {1290628}},
doi={10.1006/jctb.1994.1052},
}
Reference [57]
Carsten Thomassen, Every planar graph is $5$-choosable, J. Combin. Theory Ser. B 62 (1994), no. 1, 180–181, DOI 10.1006/jctb.1994.1062. MR1290638, Show rawAMSref\bib{ThomPlanar}{article}{
author={Thomassen, Carsten},
title={Every planar graph is $5$-choosable},
journal={J. Combin. Theory Ser. B},
volume={62},
date={1994},
number={1},
pages={180--181},
issn={0095-8956},
review={\MR {1290638}},
doi={10.1006/jctb.1994.1062},
}
Reference [58]
Carsten Thomassen, Grötzsch’s $3$-color theorem and its counterparts for the torus and the projective plane, J. Combin. Theory Ser. B 62 (1994), no. 2, 268–279, DOI 10.1006/jctb.1994.1069. MR1305053, Show rawAMSref\bib{Thom3Color}{article}{
author={Thomassen, Carsten},
title={Gr\"otzsch's $3$-color theorem and its counterparts for the torus and the projective plane},
journal={J. Combin. Theory Ser. B},
volume={62},
date={1994},
number={2},
pages={268--279},
issn={0095-8956},
review={\MR {1305053}},
doi={10.1006/jctb.1994.1069},
}
Reference [59]
Carsten Thomassen, $3$-list-coloring planar graphs of girth $5$, J. Combin. Theory Ser. B 64 (1995), no. 1, 101–107, DOI 10.1006/jctb.1995.1027. MR1328294, Show rawAMSref\bib{Thom3ListColor}{article}{
author={Thomassen, Carsten},
title={$3$-list-coloring planar graphs of girth $5$},
journal={J. Combin. Theory Ser. B},
volume={64},
date={1995},
number={1},
pages={101--107},
issn={0095-8956},
review={\MR {1328294}},
doi={10.1006/jctb.1995.1027},
}
Reference [60]
Carsten Thomassen, Color-critical graphs on a fixed surface, J. Combin. Theory Ser. B 70 (1997), no. 1, 67–100, DOI 10.1006/jctb.1996.1722. MR1441260, Show rawAMSref\bib{ThomCritical}{article}{
author={Thomassen, Carsten},
title={Color-critical graphs on a fixed surface},
journal={J. Combin. Theory Ser. B},
volume={70},
date={1997},
number={1},
pages={67--100},
issn={0095-8956},
review={\MR {1441260}},
doi={10.1006/jctb.1996.1722},
}
Reference [61]
Carsten Thomassen, A short list color proof of Grötzsch’s theorem, J. Combin. Theory Ser. B 88 (2003), no. 1, 189–192, DOI 10.1016/S0095-8956(03)00029-7. MR1974149, Show rawAMSref\bib{ThoShortlist}{article}{
author={Thomassen, Carsten},
title={A short list color proof of Gr\"otzsch's theorem},
journal={J. Combin. Theory Ser. B},
volume={88},
date={2003},
number={1},
pages={189--192},
issn={0095-8956},
review={\MR {1974149}},
doi={10.1016/S0095-8956(03)00029-7},
}
Reference [62]
Carsten Thomassen, The chromatic number of a graph of girth 5 on a fixed surface, J. Combin. Theory Ser. B 87 (2003), no. 1, 38–71, DOI 10.1016/S0095-8956(02)00027-8. Dedicated to Crispin St. J. A. Nash-Williams. MR1967881, Show rawAMSref\bib{ThoGirth5}{article}{
author={Thomassen, Carsten},
title={The chromatic number of a graph of girth 5 on a fixed surface},
note={Dedicated to Crispin St. J. A. Nash-Williams},
journal={J. Combin. Theory Ser. B},
volume={87},
date={2003},
number={1},
pages={38--71},
issn={0095-8956},
review={\MR {1967881}},
doi={10.1016/S0095-8956(02)00027-8},
}
Reference [63]
Carsten Thomassen, The number of $k$-colorings of a graph on a fixed surface, Discrete Math. 306 (2006), no. 23, 3145–3153, DOI 10.1016/j.disc.2005.04.027. MR2273145, Show rawAMSref\bib{ThomExpQuestion}{article}{
author={Thomassen, Carsten},
title={The number of $k$-colorings of a graph on a fixed surface},
journal={Discrete Math.},
volume={306},
date={2006},
number={23},
pages={3145--3153},
issn={0012-365X},
review={\MR {2273145}},
doi={10.1016/j.disc.2005.04.027},
}
Reference [64]
Carsten Thomassen, Exponentially many 5-list-colorings of planar graphs, J. Combin. Theory Ser. B 97 (2007), no. 4, 571–583, DOI 10.1016/j.jctb.2006.09.002. MR2325797, Show rawAMSref\bib{ThomWheels}{article}{
author={Thomassen, Carsten},
title={Exponentially many 5-list-colorings of planar graphs},
journal={J. Combin. Theory Ser. B},
volume={97},
date={2007},
number={4},
pages={571--583},
issn={0095-8956},
review={\MR {2325797}},
doi={10.1016/j.jctb.2006.09.002},
}
Reference [65]
Carsten Thomassen, Many 3-colorings of triangle-free planar graphs, J. Combin. Theory Ser. B 97 (2007), no. 3, 334–349, DOI 10.1016/j.jctb.2006.06.005. MR2305887, Show rawAMSref\bib{Thomany}{article}{
author={Thomassen, Carsten},
title={Many 3-colorings of triangle-free planar graphs},
journal={J. Combin. Theory Ser. B},
volume={97},
date={2007},
number={3},
pages={334--349},
issn={0095-8956},
review={\MR {2305887}},
doi={10.1016/j.jctb.2006.06.005},
}
Reference [66]
Margit Voigt, List colourings of planar graphs, Discrete Math. 120 (1993), no. 1-3, 215–219, DOI 10.1016/0012-365X(93)90579-I. MR1235909, Show rawAMSref\bib{Voigt}{article}{
author={Voigt, Margit},
title={List colourings of planar graphs},
journal={Discrete Math.},
volume={120},
date={1993},
number={1-3},
pages={215--219},
issn={0012-365X},
review={\MR {1235909}},
doi={10.1016/0012-365X(93)90579-I},
}
Reference [67]
Carl Roger Yerger Jr, Color-critical graphs on surfaces, ProQuest LLC, Ann Arbor, MI, 2010. Thesis (Ph.D.)–Georgia Institute of Technology. MR2941743, Show rawAMSref\bib{YerPhD}{book}{
author={Yerger, Carl Roger, Jr},
title={Color-critical graphs on surfaces},
note={Thesis (Ph.D.)--Georgia Institute of Technology},
publisher={ProQuest LLC, Ann Arbor, MI},
date={2010},
pages={150},
isbn={978-1124-56681-8},
review={\MR {2941743}},
}
The first author was partially supported by NSERC under Discovery Grant No. 2014-06162, the Ontario Early Researcher Awards program and the Canada Research Chairs program.
The second author was partially supported by NSF under Grant No. DMS-1202640.
Show rawAMSref\bib{3882883}{article}{
author={Postle, Luke},
author={Thomas, Robin},
title={Hyperbolic families and coloring graphs on surfaces},
journal={Trans. Amer. Math. Soc. Ser. B},
volume={5},
number={7},
date={2018},
pages={167-221},
issn={2330-0000},
review={3882883},
doi={10.1090/btran/26},
}
Settings
Change font size
Resize article panel
Enable equation enrichment
(Not available in this browser)
Note. To explore an equation, focus it (e.g., by clicking on it) and use the arrow keys to navigate its structure. Screenreader users should be advised that enabling speech synthesis will lead to duplicate aural rendering.