Minors in large almost‐5‐connected non‐planar graphs

It is shown that every sufficiently large almost‐5‐connected non‐planar graph contains a minor isomorphic to an arbitrarily large graph from one of six families of graphs. The graphs in these families are also almost‐5‐connected, by which we mean that they are 4‐connected and all 4‐separations contain a “small” side. As a corollary, every sufficiently large almost‐5‐connected non‐planar graph contains both a K_{3, 4}‐minor and a ‐minor. The connectivity condition cannot be reduced to 4‐connectivity, as there are known infinite families of 4‐connected non‐planar graphs that do not contain a K_{3, 4}‐minor. Similarly, there are known infinite families of 4‐connected non‐planar graphs that do not contain a ‐minor.     

Finding Minors in Graphs with a Given Path Structure

Given graphs G and H with , suppose that we have a ‐path in G for each edge in H. There are obvious additional conditions that ensure that G contains H as a rooted subgraph, subdivision, or immersion; we seek conditions that ensure that G contains H as a rooted minor or minor. This naturally leads to studying sets of paths that form an H‐immersion, with the additional property that paths that contain the same vertex must have a common endpoint. We say that H is contractible if, whenever G contains such an H‐immersion, G must also contain a rooted H‐minor. We show, for example, that forests, cycles, K₄, and K_{1, 1, 3} are contractible, but that graphs that are not 6‐colorable and graphs that contain certain subdivisions of K_{2, 3} are not contractible.     

Equimatchable Regular Graphs

A graph is called equimatchable if all of its maximal matchings have the same size. Kawarabayashi, Plummer, and Saito showed that the only connected equimatchable 3‐regular graphs are K₄ and K_{3, 3}. We extend this result by showing that for an odd positive integer r, if G is a connected equimatchable r‐regular graph, then . Also it is proved that for an even r, a connected triangle‐free equimatchable r‐regular graph is isomorphic to one of the graphs C₅, C₇, and .     

Minimal Obstructions for 1‐Immersions and Hardness of 1‐Planarity Testing

A graph is 1‐planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge (and any pair of crossing edges cross only once). A non‐1‐planar graph G is minimal if the graph is 1‐planar for every edge e of G. We construct two infinite families of minimal non‐1‐planar graphs and show that for every integer , there are at least nonisomorphic minimal non‐1‐planar graphs of order n. It is also proved that testing 1‐planarity is NP‐complete.     

Bipartite Intrinsically Knotted Graphs with 22 Edges

A graph is intrinsically knotted if every embedding contains a nontrivially knotted cycle. It is known that intrinsically knotted graphs have at least 21 edges and that the KS graphs, K₇ and the 13 graphs obtained from K₇ by moves, are the only minor minimal intrinsically knotted graphs with 21 edges [1, 9, 11, 12]. This set includes exactly one bipartite graph, the Heawood graph. In this article we classify the intrinsically knotted bipartite graphs with at most 22 edges. Previously known examples of intrinsically knotted graphs of size 22 were those with KS graph minor and the 168 graphs in the K_{3, 3, 1, 1} and families. Among these, the only bipartite example with no Heawood subgraph is Cousin 110 of the family. We show that, in fact, this is a complete listing. That is, there are exactly two graphs of size at most 22 that are minor minimal bipartite intrinsically knotted: the Heawood graph and Cousin 110.     

Graphs Containing Topological H

Let H denote the tree with six vertices, two of which are adjacent and of degree 3. Let G be a graph and be distinct vertices of G. We characterize those G that contain a topological H in which are of degree 3 and are of degree 1, which include all 5‐connected graphs. This work was motivated by the Kelmans–Seymour conjecture that 5‐connected nonplanar graphs contain topological K₅.     

Clique minors in double‐critical graphs

A connected t‐chromatic graph G is double‐critical if is ‐colorable for each edge . A long‐standing conjecture of Erdős and Lovász that the complete graphs are the only double‐critical t‐chromatic graphs remains open for all . Given the difficulty in settling Erdős and Lovász's conjecture and motivated by the well‐known Hadwiger's conjecture, Kawarabayashi, Pedersen, and Toft proposed a weaker conjecture that every double‐critical t‐chromatic graph contains a minor and verified their conjecture for . Albar and Gonçalves recently proved that every double‐critical 8‐chromatic graph contains a K₈ minor, and their proof is computer assisted. In this article, we prove that every double‐critical t‐chromatic graph contains a minor for all . Our proof for is shorter and computer free.     

Minimum K2, 3‐Saturated Graphs

A graph is K_{2, 3}‐saturated if it has no subgraph isomorphic to K_{2, 3}, but does contain a K_{2, 3} after the addition of any new edge. We prove that the minimum number of edges in a K_{2, 3}‐saturated graph on vertices is sat.     

A Complexity Dichotomy for the Coloring of Sparse Graphs

Galluccio, Goddyn, and Hell proved in 2001 that in any minor‐closed class of graphs, graphs with large enough girth have a homomorphism to any given odd cycle. In this paper, we study the computational aspects of this problem. Let be a monotone class of graphs containing all planar graphs, and closed under clique‐sum of order at most two. Examples of such class include minor‐closed classes containing all planar graphs, and such that all minimal obstructions are 3‐connected. We prove that for any k and g, either every graph of girth at least g in has a homomorphism to , or deciding whether a graph of girth g in has a homomorphism to is NP‐complete. We also show that the same dichotomy occurs when considering 3‐Colorability or acyclic 3‐Colorability of graphs under various notions of density that are related to a question of Havel (On a conjecture of Grünbaum, J Combin Theory Ser B 7 (1969), 184–186) and a conjecture of Steinberg (The state of the three color problem, Quo Vadis, Graph theory?, Ann Discrete Math 55 (1993), 211–248) about the 3‐Colorability of sparse planar graphs.     

Topological Minors of Cover Graphs and Dimension

We show that posets of bounded height whose cover graphs exclude a fixed graph as a topological minor have bounded dimension. This result was already proven by Walczak. However, our argument is entirely combinatorial and does not rely on structural decomposition theorems. Given a poset with large dimension but bounded height, we directly find a large clique subdivision in its cover graph. Therefore, our proof is accessible to readers not familiar with topological graph theory, and it allows us to provide explicit upper bounds on the dimension. With the introduced tools we show a second result that is supporting a conjectured generalization of the previous result. We prove that ‐free posets whose cover graphs exclude a fixed graph as a topological minor contain only standard examples of size bounded in terms of k.     

Exhaustive generation of k‐critical ‐free graphs

We describe an algorithm for generating all k‐critical ‐free graphs, based on a method of Hoàng et al. (A graph G is k‐critical H‐free if G is H‐free, k‐chromatic, and every H‐free proper subgraph of G is ‐colorable). Using this algorithm, we prove that there are only finitely many 4‐critical ‐free graphs, for both and . We also show that there are only finitely many 4‐critical ‐free graphs. For each of these cases we also give the complete lists of critical graphs and vertex‐critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3‐colorability problem in the respective classes. In addition, we prove a number of characterizations for 4‐critical H‐free graphs when H is disconnected. Moreover, we prove that for every t, the class of 4‐critical planar ‐free graphs is finite. We also determine all 52 4‐critical planar P₇‐free graphs. We also prove that every P₁₁‐free graph of girth at least five is 3‐colorable, and show that this is best possible by determining the smallest 4‐chromatic P₁₂‐free graph of girth at least five. Moreover, we show that every P₁₄‐free graph of girth at least six and every P₁₇‐free graph of girth at least seven is 3‐colorable. This strengthens results of Golovach et al.     

On Hypohamiltonian and Almost Hypohamiltonian Graphs

A graph G is almost hypohamiltonian if G is non‐hamiltonian, there exists a vertex w such that is non‐hamiltonian, and for any vertex the graph is hamiltonian. We prove the existence of an almost hypohamiltonian graph with 17 vertices and of a planar such graph with 39 vertices. Moreover, we find a 4‐connected almost hypohamiltonian graph, while Thomassen's question whether 4‐connected hypohamiltonian graphs exist remains open. We construct planar almost hypohamiltonian graphs of order n for every . During our investigation we draw connections between hypotraceable, hypohamiltonian, and almost hypohamiltonian graphs, and discuss a natural extension of almost hypohamiltonicity. Finally, we give a short argument disproving a conjecture of Chvátal (originally disproved by Thomassen), strengthen a result of Araya and Wiener on cubic planar hypohamiltonian graphs, and mention open problems.     

Leaf‐Critical and Leaf‐Stable Graphs

The minimum leaf number ml(G) of a connected graph G is defined as the minimum number of leaves of the spanning trees of G if G is not hamiltonian and 1 if G is hamiltonian. We study nonhamiltonian graphs with the property for each or for each . These graphs will be called ‐leaf‐critical and l‐leaf‐stable, respectively. It is far from obvious whether such graphs exist; for example, the existence of 3‐leaf‐critical graphs (that turn out to be the so‐called hypotraceable graphs) was an open problem until 1975. We show that l‐leaf‐stable and l‐leaf‐critical graphs exist for every integer , moreover for n sufficiently large, planar l‐leaf‐stable and l‐leaf‐critical graphs exist on n vertices. We also characterize 2‐fragments of leaf‐critical graphs generalizing a lemma of Thomassen. As an application of some of the leaf‐critical graphs constructed, we settle an open problem of Gargano et al. concerning spanning spiders. We also explore connections with a family of graphs introduced by Grünbaum in correspondence with the problem of finding graphs without concurrent longest paths.     

Matching Extension Missing Vertices and Edges in Triangulations of Surfaces

Let G be a 5‐connected triangulation of a surface Σ different from the sphere, and let be the Euler characteristic of Σ. Suppose that with even and M and N are two matchings in of sizes m and n respectively such that . It is shown that if the pairwise distance between any two elements of is at least five and the face‐width of the embedding of G in Σ is at least , then there is a perfect matching M₀ in containing M such that .     

Circumference and Pathwidth of Highly Connected Graphs

Birmele [J Graph Theory 2003] proved that every graph with circumference t has treewidth at most . Under the additional assumption of 2‐connectivity, such graphs have bounded pathwidth, which is a qualitatively stronger conclusion. Birmele's theorem was extended by Birmele et al. [Combinatorica 2007] who showed that every graph without k disjoint cycles of length at least t has treewidth . Our main result states that, under the additional assumption of ‐connectivity, such graphs have bounded pathwidth. In fact, they have pathwidth . Moreover, examples show that ‐connectivity is required for bounded pathwidth to hold. These results suggest the following general question: for which values of k and graphs H does every k‐connected H‐minor‐free graph have bounded pathwidth? We discuss this question and provide a few observations.     

Retracts of Products of Chordal Graphs

In this article, we characterize the graphs G that are the retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain K_{2, 3}, the 4‐wheel minus one spoke , and the k‐wheels (for as induced subgraphs. We also show that these graphs G are exactly the cage‐amalgamation graphs as introduced by Bre?ar and Tepeh Horvat (Cage‐amalgamation graphs, a common generalization of chordal and median graphs, Eur J Combin 30 (2009), 1071–1081); this solves the open question raised by these authors. Finally, we prove that replacing all products of cliques of G by products of Euclidean simplices, we obtain a polyhedral cell complex which, endowed with an intrinsic Euclidean metric, is a CAT(0) space. This generalizes similar results about median graphs as retracts of hypercubes (products of edges) and median graphs as 1‐skeletons of CAT(0) cubical complexes. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 161–180, 2013     

Uniquely Cycle‐Saturated Graphs

Given a graph F, a graph G is uniquely F‐saturated if F is not a subgraph of G and adding any edge of the complement to G completes exactly one copy of F. In this article, we study uniquely ‐saturated graphs. We prove the following: (1) a graph is uniquely C₅‐saturated if and only if it is a friendship graph. (2) There are no uniquely C₆‐saturated graphs or uniquely C₇‐saturated graphs. (3) For , there are only finitely many uniquely ‐saturated graphs (we conjecture that in fact there are none). Additionally, our results show that there are finitely many k‐friendship graphs (as defined by Kotzig) for .     

Improvements on the density of maximal 1‐planar graphs

A graph is 1‐planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1‐planar drawing is called 1‐plane. A graph is maximal 1‐planar (1‐plane), if we cannot add any missing edge so that the resulting graph is still 1‐planar (1‐plane). Brandenburg et al. showed that there are maximal 1‐planar graphs with only edges and maximal 1‐plane graphs with only edges. On the other hand, they showed that a maximal 1‐planar graph has at least edges, and a maximal 1‐plane graph has at least edges. We improve both lower bounds to .     

On (4, 2)‐Choosable Graphs

A graph G is called ‐choosable if for any list assignment L that assigns to each vertex v a set of a permissible colors, there is a b‐tuple L‐coloring of G . An (a , 1)‐choosable graph is also called a‐choosable. In the pioneering article on list coloring of graphs by Erd?s et al.  2 , 2‐choosable graphs are characterized. Confirming a special case of a conjecture in  2 , Tuza and Voigt  3 proved that 2‐choosable graphs are ‐choosable for any positive integer m . On the other hand, Voigt 6 proved that if m is an odd integer, then these are the only ‐choosable graphs; however, when m is even, there are ‐choosable graphs that are not 2‐choosable. A graph is called 3‐choosable‐critical if it is not 2‐choosable, but all its proper subgraphs are 2‐choosable. Voigt conjectured that for every positive integer m , all bipartite 3‐choosable‐critical graphs are ‐choosable. In this article, we determine which 3‐choosable‐critical graphs are (4, 2)‐choosable, refuting Voigt's conjecture in the process. Nevertheless, a weaker version of the conjecture is true: we prove that there is an even integer k such that for any positive integer m , every bipartite 3‐choosable‐critical graph is ‐choosable. Moving beyond 3‐choosable‐critical graphs, we present an infinite family of non‐3‐choosable‐critical graphs that have been shown by computer analysis to be (4, 2)‐choosable. This shows that the family of all (4, 2)‐choosable graphs has rich structure.