We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the torus, with the exception of two specific infinite families of “Petersen-like” graphs, is 3-edge-colorable. This shows that every toroidal snark can be obtained from several copies of the Petersen graph using the dot product operation. The first two snarks in this family are the Petersen graph and one of the Blanuša snarks; the rest were exposed by Belcastro and Kaminski and by Vodopivec. This proves a strengthening of the well-known, long-standing conjecture of Grünbaum from 1968.

A map is a \(2\) -cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. An automorphism of a map can be thought of as a permutation of the vertices, which preserves the vertex-edge-face incidences in the embedding. Every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no “truly subquadratic” algorithm for testing map isomorphism for unconstrained genus, we present a linear-time algorithm for computing the generators of the automorphism group of a map on an orientable surface of genus \(g\neq 0\) , parametrized by the genus \(g\) . A map on an orientable surface is uniform if the cyclic vector of sizes of faces incident to a vertex \(v\) does not depend on the choice of \(v\) . The algorithm applies a sequence of local reductions and produces a uniform map while preserving the automorphism group. The automorphism group of the original map can be reconstructed from the automorphism group of the associated uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover. The algorithm can be used to solve the map isomorphism problem between maps (orientable or non-orientable) of bounded negative Euler characteristic.

We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the projective plane, with the single exception of the Petersen graph, is 3-edge-colorable. In other words, the only (nontrivial) snark that can be embedded in the projective plane is the Petersen graph. This implies that a 2-connected cubic (multi)graph that can be embedded in the projective plane is not 3-edge-colorable if and only if it can be obtained from the Petersen graph by replacing each vertex by a 2-edge-connected planar cubic (multi)graph. Here, a replacement of a vertex$v$in a cubic graph$G$is the operation that takes a 2-connected planar (cubic) multigraph$H$containing some vertex$u$of degree 3, unifying$G-v$and$H-u$, and connecting the vertices in$N_{G}[v]$in$G-v$with the three neighbors of$u$in$H-u$with 3 edges. Any graph obtained in such a way is said to be Petersen-like. This result is a nontrivial generalization of the Four Color Theorem, and its proof requires a combination of extensive computer verification and computer-free extension of existing proofs on colorability. Using this result, we obtain the following algorithmic consequence. Input: A cubic graph$G$. Output: Either a 3-edge-coloring of$G$, an obstruction showing that$G$is not 3-edge-colorable, or the conclusion that$G$cannot be embedded in the projective plane (certified by exposing a forbidden minor for the projective plane contained in$G$). Time complexity:$O(n^{2})$, where$n=\vert V(G)\vert$. An unexpected consequence of this result is a coloring-flow duality statement for the projective plane: A cubic graph embedded in the projective plane is 3-edge-colorable if and only if its dual multigraph is 5-vertex-colorable. Moreover, we show that a 2-edge connected graph embedded in the projective plane admits a nowhere-zero 4-flow unless it is Petersen-like (in which case it does not admit nowhere-zero 4-flows). This proves a strengthening of the Tutte 4-flow conjecture for graphs on the projective plane. Some of our proofs require extensive computer verification. The necessary source codes, together with the input and output files and the complete set of more than 5000 reducible configurations, are available on Github11https://github.com/edge-coloring. Refer to the “README.md” file in each directory for instructions on how to run each program. which can be considered as an addendum to this paper. Moreover, we provide pseudocodes for all our computer verifications.

We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an n-vertex planar graph whose vertices are partitioned into independent sets (called clusters) with paths - one for each cluster - that connect all the vertices in each cluster while maintaining planarity. We show that the problem can be solved in time 2^𝒪(n) for both the variable and fixed embedding case. Moreover, we show that it can be solved in subexponential time 2^𝒪(√n log n) in the fixed embedding case if additionally the input graph is connected. The latter time complexity is tight under the Exponential-Time Hypothesis. We also show that n can be replaced with the vertex cover number of the input graph by providing a linear (resp. polynomial) kernel for the variable-embedding (resp. fixed-embedding) case; these results contrast the NP-hardness of the problem on graphs of bounded treewidth (and even on trees). Finally, we complement known lower bounds for the problem by showing that Clustered Planarity with Linear Saturators is NP-hard even when the number of clusters is at most 3, thus excluding the algorithmic use of the number of clusters as a parameter.

A random 2-cell embedding of a connected graph G in some orientable surface is obtained by choosing a random local rotation around each vertex. Under this setup, the number of faces or the genus of the corresponding 2-cell embedding becomes a random variable. Random embeddings of two particular graph classes - those of a bouquet of n loops and those of n parallel edges connecting two vertices - have been extensively studied and are well-understood. However, little is known about more general graphs despite their important connections with central problems in mainstream mathematics and in theoretical physics (see [Lando & Zvonkin, Graphs on surfaces and their applications, Springer 2004]). There are also tight connections with problems in computing (random generation, approximation algorithms). The results of this paper, in particular, explain why Monte Carlo methods (see, e.g., [Gross & Tucker, Local maxima in graded graphs of imbeddings, Ann. NY Acad. Sci 1979] and [Gross & Rieper, Local extrema in genus stratified graphs, JGT 1991]) cannot work for approximating the minimum genus of graphs.

The main results of this paper provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. By dense we mean that \(|E(G)|\ge \alpha \, |V(G)|^2\) for some fixed \(\alpha \gt 0\) . While a constant-factor approximation is trivial for this class of graphs, approximations with factor arbitrarily close to 1 need a sophisticated algorithm and complicated mathematical justification. More precisely, we provide an algorithm that for a given (dense) graph G of order n and given \(\varepsilon \gt 0\) , returns an integer g such that G has an embedding in a surface of genus g , and this is ɛ-close to a minimum genus embedding in the sense that the minimum genus \(\mathsf {g}(G)\) of G satisfies: \(\mathsf {g}(G)\le g\le (1+\varepsilon)\mathsf {g}(G)\) . The running time of the algorithm is \(O(f(\varepsilon)\,n^2)\) , where \(f(\cdot)\) is an explicit function. Next, we extend this algorithm to also output an embedding (rotation system) whose genus is g . This second algorithm is an Efficient Polynomial-time Randomized Approximation Scheme (EPRAS) and runs in time \(O(f_1(\varepsilon)\,n^2)\) . Our algorithms are based on the analysis of minimum genus embeddings of quasirandom graphs. We use a general notion of quasirandom graphs [ 25 ]. We start with a regular partition obtained via an algorithmic version of the Szemerédi Regularity Lemma (due to Frieze and Kannan [ 17 ] and to Fox, Lovász, and Zhao [ 14 , 15 ]). We then partition the input graph into a bounded number of quasirandom subgraphs, which are preselected in such a way that they admit embeddings using as many triangles and quadrangles as faces as possible. Here we provide an ɛ-approximation \(\nu (G)\) for the maximum number of edge-disjoint triangles in G . The value \(\nu (G)\) can be computed by solving a linear program whose size is bounded by certain value \(f_2(\varepsilon)\) depending only on ɛ. After solving the linear program, the genus can be approximated (see Corollary 1.7 ). The proof of this result is long and will be of independent interest in topological graph theory.

Abstract. A circle graph is an intersection graph of a set of chords of a circle. We describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the “usual suspects.” Our results imply that treewidth and Hadwiger number are linearly tied on the class of circle graphs and that the unavoidable induced subgraphs of a vertex-minor-closed class with large treewidth are the usual suspects if and only if the class has bounded rank-width. Using the same tools, we also study the treewidth of graphs [Formula: see text] that have a circular drawing whose crossing graph is well-behaved in some way. In this setting, we show that if the crossing graph is [Formula: see text]-minor-free, then [Formula: see text] has treewidth at most [Formula: see text] and has no [Formula: see text]-topological minor. On the other hand, we show that there are graphs with arbitrarily large Hadwiger number that have circular drawings whose crossing graphs are 2-degenerate.

Abstract. For an abelian group [Formula: see text], a graph [Formula: see text] is said to be [Formula: see text]-flow-critical if [Formula: see text] does not admit a nowhere-zero [Formula: see text]-flow, but for each edge [Formula: see text], the contraction [Formula: see text] has a nowhere-zero [Formula: see text]-flow. We obtain a bound on the density of [Formula: see text]-flow-critical graphs drawn on a fixed surface, generalizing the planar case of the bound on the density of 4-critical graphs by Kostochka and Yancey.

A map is a 2-cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. An automorphism of a map can be thought of as a permutation of the vertices which preserves the vertex-edge-face incidences in the embedding. When the underlying surface is orientable, every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no "truly subquadratic" algorithm for testing map isomorphism for unconstrained genus, we present a linear-time algorithm for computing the generators of the automorphism group of a map, parametrized by the genus of the underlying surface. The algorithm applies a sequence of local reductions and produces a uniform map, while preserving the automorphism group. The automorphism group of the original map can be reconstructed from the automorphism group of the uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover.

The game of Cops and Robbers is a well-known game played on graphs. In this paper, we consider the class of graphs of bounded diameter. We improve the strategy of cops and the previously used probabilistic method, which results in an improved upper bound for the cop number of graphs of bounded diameter. In particular, for graphs of diameter 4, we improve the upper bound from $n^{\frac{2}{3}+o(1)}$ to $n^{\frac{3}{5}+o(1)}$ and for diameter 3 from $n^{\frac{2}{3}+o(1)}$ to $n^{\frac{4}{7}+o(1)}$.

We study $c$-crossing-critical graphs, which are the minimal graphs that require at least $c$ edge-crossings when drawn in the plane. For every fixed pair of integers with $c\ge 13$ and $d\ge 1$, we give first explicit constructions of $c$-crossing-critical graphs containing a vertex of degree greater than $d$. We also show that such unbounded degree constructions do not exist for $c\le 12$, precisely, that there exists a constant $D$ such that every $c$-crossing-critical graph with $c\le 12$ has maximum degree at most $D$. Hence, the bounded maximum degree conjecture of $c$-crossing-critical graphs, which was generally disproved in 2010 by Dvořák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values $c\le 12.$

We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For c=1 there are only two such graphs without degree-2 vertices, K_5 and K_{3,3}, but for any fixed c>1 there exist infinitely many c-crossing-critical graphs. It has been previously shown that c-crossing-critical graphs have bounded path-width and contain only a bounded number of internally disjoint paths between any two vertices. We expand on these results, providing a more detailed description of the structure of crossing-critical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded path-width. Then we show that every c-crossing-critical graph can be obtained from a c-crossing-critical graph of bounded size by replicating bounded-size parts that already appear in narrow "bands" or "fans" in the graph. This also gives an algorithm to generate all the c-crossing-critical graphs of at most given order n in polynomial time per each generated graph.

We consider the problem of deciding whether an input graph G admits a topological embedding into a two-dimensional simplicial complex C. This problem includes, among others, the embeddability problem of a graph on a surface and the topological crossing number of a graph, but is more general. The problem is NP-complete when C is part of the input, and we give a polynomial-time algorithm if the complex C is fixed. Our strategy is to reduce the problem to an embedding extension problem on a surface, which has the following form: Given a subgraph H' of a graph G', and an embedding of H' on a surface S, can that embedding be extended to an embedding of G' on S? Such problems can be solved, in turn, using a key component in Mohar's algorithm to decide the embeddability of a graph on a fixed surface (STOC 1996, SIAM J. Discr. Math. 1999).

The results of this paper provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. The running time of the algorithm is quadratic. Moreover, we extend the algorithm to output an embedding (rotation system), whose genus is arbitrarily close to the minimum genus. This second algorithm is an Efficient Polynomial-time Randomized Approximation Scheme (EPRAS) and the expected running time is also quadratic.

Motivated by a problem about totally odd immersions of graphs, we define the odd edge-connectivity λo(u, υ) as the maximum number of edge-disjoint trails of odd length from u to υ. It was recently discovered that λo(u, υ) can be approximated up to a constant multiplicative factor using the usual edge-connectivity between u and v and the minimum value of another parameter that measures “how far from a bipartite graph” the part of the graph around u and v is. In this paper, we formalize this second ingredient and call it the perimeter. We prove that perimeter is a submodular function on the vertex-sets of a graph. Using this fact, we obtain a version of the Gomory–Hu Theorem in which minimum edge-cuts are replaced by sets of minimum perimeter. We construct (in polynomial time) a rooted forest structure, analogous to the Gomory-Hu tree of a graph, which encodes a collection of minimum-perimeter vertex-sets. Although the classical Gomory-Hu Theorem extends to arbitrary symmetric submodular functions, our result is novel and indicates a possibility for further generalizations. These results have significant implications for the study of path and trail systems with parity constraints. We present two such applications: an efficient data structure for storing approximate odd edge-connectivities for all pairs of vertices in a graph, and a rough structure theorem for graphs with no “totally odd” immersion of a large complete graph.

The Harary--Hill conjecture, still open after more than 50 years, asserts that the crossing number of the complete graph $K_n$ is \(H(n) := \frac 1 4 łfloor\fracn2\rfloor łfloor\fracn-12\rfloor łfloor\fracn-22\rfloor łfloor\fracn-32\rfloor.\) Ábrego et al. [ Discrete Comput. Geom., 52 (2014), pp. 743--753] introduced the notion of shellability of a drawing $D$ of $K_n$. They proved that if $D$ is $s$-shellable for some $s\geq\lfloor\frac{n}{2}\rfloor$, then $D$ has at least $H(n)$ crossings. This is the first combinatorial condition on a drawing that guarantees at least $H(n)$ crossings. In this work, we generalize the concept of $s$-shellability to bishellability, where the former implies the latter in the sense that every $s$-shellable drawing is, for any $b \leq s-2$, also $b$-bishellable. Our main result is that $(\lfloor \frac{n}{2} \rfloor-2)$-bishellability of a drawing $D$ of $K_n$ also guarantees, with a simpler proof than for $s$-shellability, that $D$ has at least $H(n)$ crossings. We exhibit a drawing of $K_{11}$ that has $H(11)$ crossings, is 3-bishellable, and is not $s$-shellable for any $s\geq5$. This shows that we have properly extended the class of drawings for which the Harary--Hill conjecture is proved. Moreover, we provide an infinite family of drawings of $K_n$ that are $(\lfloor \frac{n}{2} \rfloor-2)$-bishellable, but not $s$-shellable for any $s\geq\lfloor\frac{n}{2}\rfloor$.

Motivated by a problem asked by Richter and by the long standing Harary--Hill conjecture, we study the relation between the crossing number of a graph $G$ and the crossing number of its cone $CG$, the graph obtained from $G$ by adding a new vertex adjacent to all the vertices in $G$. Simple examples show that the difference $cr(CG)-cr(G)$ can be arbitrarily large for any fixed $k=cr(G)$. In this work, we are interested in finding the smallest possible difference; that is, for each nonnegative integer $k$, find the smallest $f(k)$ for which there exists a graph with crossing number at least $k$ and cone with crossing number $f(k)$. For small values of $k$, we give exact values of $f(k)$ when the problem is restricted to simple graphs and show that $f(k)=k+\Theta (\sqrt {k})$ when multiple edges are allowed.

We present a polynomial-time 9/7-approximation algorithm for the graphic TSP for cubic graphs, which improves the previously best approximation factor of 1.3 for 2-connected cubic graphs and drops the requirement of 2-connectivity at the same time. To design our algorithm, we prove that every simple 2-connected cubic n-vertex graph contains a spanning closed walk of length at most 9n/7-1, and that such a walk can be found in polynomial time.

Neumann-Lara conjectured in 1985 that every planar digraph with digirth at least three is 2-colorable, meaning that the vertices can be 2-colored without creating any monochromatic directed cycles. We prove a relaxed version of this conjecture: every planar digraph of digirth at least four is 2-colorable.

Despite Menger's famous duality between packings and coverings of (u, v)-paths in a graph, there is no duality when we require the paths be odd: a graph with no two edge-disjoint odd (u, v)-paths may need an arbitrarily large number of edges to cover all such paths. In this paper, we study the relaxed problem of packing odd trails. Our main result is an approximate duality for odd trails: if ν(u, v) denotes the maximum number of edge-disjoint (u, v)-trails of odd length in a graph G and τ(u, v) denotes the minimum number of edges that intersect every such trail, then The proof leads to a polynomial-time algorithm to find, for any given k, either k edge-disjoint odd (u, v)-trails or a set of fewer than 8k edges intersecting all odd (u, v)-trails. This yields a constant factor approximation algorithm for the packing number ν(u, v). This result generalizes to the setting of signed graphs and to the setting of group-labelled graphs, in which case “odd length” is replaced by “non-unit product of labels”. The motivation for this result comes from the study of totally odd graph immersions, and our results explain, in particular, why there is an essential difference between the totally odd weak and strong immersions.

A graph with four special vertices (called terminals) is wye-delta reducible if we can obtain a graph on four vertices by a sequence of wye-delta and delta-wye operations and series-parallel reductions, none of which is allowed to remove any of the terminals. A good characterization of wye-delta reducible 3-connected planar graphs with four terminals is given. The proofs yield an O(n2) time algorithm that either exhibits an obstruction to the 4-terminal reducibility or returns a sequence of wye-delta operations and series-parallel reductions that reduce the input graph to a subgraph of K4 whose vertices are the terminals. We also discuss terminal wye-delta reducibility when a mixture of vertices and faces are treated as terminals. It is also shown that a sufficiently connected cubic graph is wye-delta reducible if and only if it does not contain the Petersen graph as a minor. The main ingredient in the proofs is a good characterization of planar graphs with four terminals that do not admit a rooted K2,4 minor with the four terminals corresponding to the roots on the large side of the bipartition of K2,4. Up to small connectivity reductions, cases without the rooted minor fall into five structural cases that lead to a polynomial-time algorithm for recognition of these graphs and construction of rooted K2,4 minors. This result is of independent interest in structural graph theory.

We solve two open problems regarding the classification of certain classes of Cayley graphs with integer eigenvalues. We first classify all finite groups that have a nontrivial Cayley graph with integer eigenvalues, thus solving a problem proposed by Abdollahi and Jazaeri. The notion of Cayley integral groups was introduced by Klotz and Sander. These are groups for which every Cayley graph has only integer eigenvalues. In the second part of the paper, all Cayley integral groups are determined.

Tuza conjectured that for every graph $G$ the maximum size $\nu$ of a set of edge-disjoint triangles and minimum size $\tau$ of a set of edges meeting all triangles satisfy $\tau \leq 2\nu$. We consider an edge-weighted version of this conjecture, which amounts to packing and covering triangles in multigraphs. Several known results about the original problem are shown to be true in this context, and some are improved. In particular, we answer a question of Krivelevich, who proved that $\tau \leq 2\nu^*$ (where $\nu^*$ is the fractional version of $\nu$) and asked whether this is tight. We prove that $\tau \leq 2\nu^*-\frac{1}{\sqrt{6}}\sqrt{\nu^*}$ and show that this bound is essentially best possible.

It is proved that every graph embedded on a (nonspherical) surface with nonseparating face-width at least 7 contains a minor isomorphic to $K_6$. It is also shown that face-width four yields the same conclusion for graphs on the projective plane.

A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show the surprising fact that it is NP-hard to compute the crossing number of near-planar graphs. A graph is 1-planar if it has a drawing where every edge is crossed by at most one other edge. We show that it is NP-hard to decide whether a given near-planar graph is 1-planar. The main idea in both reductions is to consider the problem of simultaneously drawing two planar graphs inside a disk, with some of its vertices fixed at the boundary of the disk. This leads to the concept of anchored embedding, which is of independent interest. As an interesting consequence we obtain a new, geometric proof of NP-completeness of the crossing number problem, even when restricted to cubic graphs. This resolves a question of Hliněný.

Let $D$ be a digraph. The chromatic number $\chi(D)$ of $D$ is the smallest number of colors needed to color the vertices of $D$ such that every color class induces an acyclic subdigraph. The girth of $D$ is the length of a shortest directed cycle, or $\infty$ if $D$ is acyclic. Let $G(k,n)$ be the maximum possible girth of a digraph on $n$ vertices with $\chi(D) > k$. It is shown that $G(k,n) \ge \left\lfloor n^{1/k}\right\rfloor$ and $G(k,n) \le (3\log_2 n \log_2\log_2 n)^{1-1/k} n^{1/k}$ for $n \ge 3$ and $k \ge 2$.

It is well known that every planar or projective planar graph can be 3-colored so that each color class induces a forest. This bound is sharp. In this paper, we show that there are in fact exponentially many 3-colorings of this kind for any (projective) planar graph. The same result holds in the setting of 3-list-colorings.

A classical theorem of Gallai states that in every graph that is critical for k-colorings, the vertices of degree $k-1$ induce a tree-like graph whose blocks are either complete graphs or cycles of odd length. We provide a generalization to colorings and list colorings of digraphs, where some new phenomena arise. In particular, the problem of list coloring digraphs with the lists at each vertex v having $\min\{d^{+}(v),d^{-}(v)\}$ colors turns out to be NP-hard.

A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show that it is NP-hard to compute the crossing number of near-planar graphs. The main idea in the reduction is to consider the problem of simultaneously drawing two planar graphs inside a disk, with some of its vertices fixed at the boundary of the disk. This approach can be used to prove hardness of some other geometric problems. As an interesting consequence we obtain a new, geometric proof of NP-completeness of the crossing number problem, even when restricted to cubic graphs. This resolves a question of Hlinený.

We consider piecewise linear embeddings of graphs in 3-space ℜ3. Such an embbeding is linkless if every pair of disjoint cycles forms a trivial link (in the sense of knot theory). Robertson, Seymour and Thomas [47] showed that a graph has a linkless embedding in ℜ3 if, and only if, it does not contain as a minor any of seven graphs in Petersen's family (graphs obtained from K6 by a series of YΔ and ΔY operations). They also showed that a graph is linklessly embeddable in ℜ3 if, and only if, it admits a flat embedding into ℜ3, i.e. an embedding such that for every cycle C of G there exists a closed 2-disk D ⊆ ℜ3 with D ∩ G = ∂D = C. Clearly, every flat embeddings is linkless, but the converse is not true. We first consider the following algorithmic problem associated with embeddings in ℜ3:

It is proved that every graph embedded in a fixed surface with sufficiently large edge-width is acyclically 7-colorable and that its star chromatic number is at most $2s_0^*+3$, where $s_0^*\leq20$ is the maximum star chromatic number for the class of all planar graphs.

A cycle on a combinatorial surface is tight if it as short as possible in its (free) homotopy class. We describe an algorithm to compute a single tight, noncontractible, essentially simple cycle on a given orientable combinatorial surface in O ( n log n ) time. The only method previously known for this problem was to compute the globally shortest noncontractible or nonseparating cycle in O (min{ g 3 , n }, n log n ) time, where g is the genus of the surface. As a consequence, we can compute the shortest cycle freely homotopic to a chosen boundary cycle in O ( n log n ) time, a tight octagonal decomposition in O ( gn log n ) time, and a shortest contractible cycle enclosing a nonempty set of faces in O ( n log 2 n ) time.

A k-list-assignment for a graph G assigns to each vertex v of G a list L(v) of admissible colors, where |L(v)| ≥ k. A graph is k-list-colorable (or k-choosable) if it can be properly colored from the lists for every k-list-assignment. We prove the following conjecture posed by Thomassen in 1994: “There are only finitely many list-color-critical graphs with all lists of cardinality at least 5 on any fixed surface.” This generalizes the well-known result of Thomassen on the usual graph coloring case. We use this theorem and specific parts of its proof to resolve the complexity status of the following problem about k-list-coloring graphs on a fixed surface S, where k is a fixed positive integer. Input: A graph G embedded in the surface S. Question: Is G k-choosable? If not, provide a certificate (a list-color-critical subgraph and the corresponding k-list-assignment). The cases k = 3, 4 are known to be NP-hard (actually even -complete), and the cases k = 1, 2 are easy. Our main results imply that the problem is tractable for every k ≥ 5. In fact, together with our recent algorithmic result, we are able to solve it in linear time when k ≥ 5. Our proof yields even more: if the input graph is k-list-colorable, then for any k-listassignment L, we can construct an L-coloring of G in linear time. This generalizes the well-known linear-time algorithms for planar graphs by Nishizeki and Chiba (for 5-coloring), and Thomassen (for 5-list-coloring). We also give a polynomial-time algorithm to resolve the following question: Input: A graph G in the surface S, and a k-listassignment L, where k = 5. Question: Does G admit an L-coloring? If not, provide a certificate for this. If yes, then return an L-coloring. If the graph G is k-list-colorable, then our first result gives a linear time solution. However, the second problem is more general, since it provides a coloring (or a small obstruction) for an arbitrary graph in S. We also use our main theorem to prove another conjecture that was proposed recently by Thomassen: “For every fixed surface S, there exists a positive constant c such that every 5-list-colorable graph with n vertices embedded on S, has at least c·2n distinct 5-listcolorings for every 5-list-assignment for G.” Thomassen himself proved that this conjecture holds for usual 5-colorings. In addition to all these results, we also made partial progress towards a conjecture of Albertson concerning coloring extensions and a progress on similar questions for triangle-free graphs and graphs of larger girth.

The two-coloring number of graphs, which was originally introduced in the study of the game chromatic number, also gives an upper bound on the degenerate chromatic number as introduced by Borodin. It is proved that the two-coloring number of any planar graph is at most nine. As a consequence, the degenerate list chromatic number of any planar graph is at most nine. It is also shown that the degenerate diagonal chromatic number is at most 11 and the degenerate diagonal list chromatic number is at most 12 for all planar graphs.

The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. Our main result is that every graph G that does not contain a fixed graph as a minor has crossing number O(Δn), where G has n vertices and maximum degree Δ. This dependence on n and Ø is best possible. This result answers an open question of Wood and Telle [New York J. Mathematics, 2007], who proved the best previous bound of O(Ø2n).

For every fixed surface S, orientable or non-orientable, and a given graph G, Mohar (STOC'96 and Siam J. Discrete Math. (1999)) described a linear time algorithm which yields either an embedding of G in S or a minor of G which is not embeddable in S and is minimal with this property. That algorithm, however, needs a lot of lemmas which spanned six additional papers. In this paper, we give a new linear time algorithm for the same problem. The advantages of our algorithm are the following: 1. The proof is considerably simpler: it needs only about 10 pages, and some results (with rather accessible proofs) from graph minors theory, while Mohar's original algorithm and its proof occupy more than 100 pages in total. 2. The hidden constant (depending on the genus g of the surface S) is much smaller. It is singly exponential in g, while it is doubly exponential in Mohar's algorithm. As a spinoff of our main result, we give another linear time algorithm, which is of independent interest. This algorithm computes the genus and constructs minimum genus embeddings of graphs of bounded tree-width. This resolves a conjecture by Neil Robertson and solves one of the most annoying long standing open question about complexity of algorithms on graphs of bounded tree-width.

For every surface S (orientable or non-orientable), we give a linear time algorithm to test the graph isomorphism of two graphs, one of which admits an embedding of face-width at least 3 into S. This improves a previously known algorithm whose time complexity is nO(g), where g is the genus of S. This is the first algorithm for which the degree of polynomial in the time complexity does not depend on g. The above result is based on two linear time algorithms, each of which solves a problem that is of independent interest. The first of these problems is the following one. Let S be a fixed surface. Given a graph G and an integer k ≥ 3, we want to find an embedding of G in S of face-width at least k, or conclude that such an embedding does not exist. It is known that this problem is NP-hard when the surface is not fixed. Moreover, if there is an embedding, the algorithm can give all embeddings of face-width at least k, up to Whitney equivalence. Here, the face-width of an embedded graph G is the minimum number of points of G in which some non-contractible closed curve in the surface intersects the graph. In the proof of the above algorithm, we give a simpler proof and a better bound for the theorem by Mohar and Robertson concerning the number of polyhedral embeddings of 3-connected graphs. The second ingredient is a linear time algorithm for map isomorphism and Whitney equivalence. This part generalizes the seminal result of Hopcroft and Wong that graph isomorphism can be decided in linear time for planar graphs.

The unit distance graph $\mathcal{R}$ is the graph with vertex set $\mathbb{R}^2$ in which two vertices (points in the plane) are adjacent if and only if they are at Euclidean distance 1. We prove that the circular chromatic number of $\mathcal{R}$ is at least 4, thus improving the known lower bound of $32/9$ obtained from the fractional chromatic number of $\mathcal{R}$.

It is well-known (Feige and Kilian [24], Håstad [39]) that approximating the chromatic number within a factor of n1-ε cannot be done in polynomial time for ε>0, unless coRP = NP. Computing the list-chromatic number is much harder than determining the chromatic number. It is known that the problem of deciding if the list-chromatic number is k, where k ≥ 3, is Π2p-complete [37].In this paper, we focus on minor-closed and odd-minor-closed families of graphs. In doing that, we may as well consider only graphs without Kk-minors and graphs without odd Kk-minors for a fixed value of k, respectively. Our main results are that there is a polynomial time approximation algorithm for the list-chromatic number of graphs without Kk-minors and there is a polynomial time approximation algorithm for the chromatic number of graphs without odd-Kk-minors. Their time complexity is O(n3) and O(n4), respectively. The algorithms have multiplicative error O(√log k) and additive error O(k), and the multiplicative error occurs only for graphs whose list-chromatic number and chromatic number are Θ(k), respectively.Let us recall that H has an odd complete minor of order l if there are l vertex disjoint trees in H such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic. Let us observe that the complete bipartite graph Kn/2,n/2 contains a Kk-minor for k ≤ n/2, but on the other hand, it does not contain an odd Kk-minor for any k ≥ 3. Odd K5-minor-free graphs are closely related to one field of discrete optimization which is finding conditions under which a given polyhedron has integer vertices, so that integer optimization problems can be solved as linear programs. See [33, 34, 64]. Also, the odd version of the well-known Hadwiger's conjecture has been considered, see [28].Our main idea involves precoloring extension. This idea is used in many results; one example is Thomassen's proof on his celebrated theorem on planar graphs [69].The best previously known approximation for the first result is a simple O(k √log k)-approximation following algorithm that guarantees a list-coloring with O(k √log k) colors for Kk-minor-free graphs. This follows from results of Kostochka [54, 53] and Thomason [67, 68].The best previous approximation for the second result comes from the recent result of Geelen et al. [28] who gave an O(k √log k)-approximation algorithm.We also relate our algorithm to the well-known conjecture of Hadwiger [38] and its odd version. In fact, we give an O(n3) algorithm to decide whether or not a weaker version of Hadwiger's conjecture is true. Here, by a weaker version of Hadwiger's conjecture, we mean a conjecture which says that any 27k-chromatic graph contains a Kk-minor. Also, we shall give an O(n2500k) algorithm for deciding whether or not any 2500k-chromatic graph contains an odd-Kk-minor.Let us mention that this presentation consists of two papers which are merged into this one. The first one consists of results concerning minor-closed classes of graphs by two current authors, and the other consists of results concerning odd-minor-closed classes of graphs by the first author.

The minor crossing number of a graph G is defined as the minimum crossing number of all graphs that contain G as a minor. Basic properties of this new invariant are presented. We study topological structure of graphs with bounded minor crossing number and obtain a new strong version of a lower bound based on the genus. We also give a generalization of an inequality of Moreno and Salazar crossing numbers of a graph and its minors.

An acyclic homomorphism of a digraph D into a digraph F is a mapping $\phi\colon V(D) \to V(F)$ such that for every arc $uv\in E(D)$, either $\phi(u)=\phi(v)$ or $\phi(u)\phi(v)$ is an arc of F, and for every vertex $v\in V(F)$, the subgraph of D induced on $\phi^{-1}(v)$ is acyclic. For each fixed digraph F we consider the following decision problem: Does a given input digraph D admit an acyclic homomorphism to F? We prove that this problem is NP-complete unless F is acyclic, in which case it is polynomial time solvable. From this we conclude that it is NP-complete to decide if the circular chromatic number of a given digraph is at most q, for any rational number $q > 1$. We discuss the complexity of the problems restricted to planar graphs. We also refine the proof to deduce that certain F-coloring problems are NP-complete.

For an arbitrary fixed surface S, a linear time algorithm is presented that for a given graph G either finds an embedding of G in S or identifies a subgraph of G that is homeomorphic to a minimal forbidden subgraph for embeddability in S. A side result of the proof of the algorithm is that minimal forbidden subgraphs for embeddability in S cannot be arbitrarily large. This yields a constructive proof of the result of Robertson and Seymour that for each closed surface there are only finitely many minimal forbidden subgraphs. The results and methods of this paper can be used to solve more general embedding extension problems.

Let $K=C\cup e_1\cup e_2$ be a subgraph of G consisting of a cycle C and disjoint paths e1 and e2 connecting two interlacing pairs of vertices in C. Suppose that K is embedded in the Möbius band in such a way that C lies on its boundary. An algorithm is presented which in linear time extends the embedding of K to an embedding of G, if such an extension is possible, or finds a "nice" obstruction for such embedding extensions. The structure of obtained obstructions is also analyzed in detail.

Article Embedding graphs in an arbitrary surface in linear time Share on Author: Bojan Mohar Department of Mathematics, University of Ljubljana, Jadranska 19, 61111 Ljubljana, Slovenia Department of Mathematics, University of Ljubljana, Jadranska 19, 61111 Ljubljana, SloveniaView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 392–397https://doi.org/10.1145/237814.237986Online:01 July 1996Publication History 25citation480DownloadsMetricsTotal Citations25Total Downloads480Last 12 Months9Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access