Forbidding Kuratowski Graphs as Immersions

Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs (K₅ and K_{3, 3}) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch‐width at most 10 by repetitively applying i‐edge‐sums, for . We also use this result to give a structural characterization of graphs that exclude K_{3, 3} as an immersion.     

Minor‐universal planar graphs without accumulation points

We show that the countably infinite union of infinite grids, H say, is minor‐universal in the class of all graphs that can be drawn in the plane without vertex accumulation points, i.e., that H contains every such graph as a minor. Furthermore, we characterize the graphs that occur as minors of the infinite grid by a natural topological condition on their embeddings. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 1–7, 2001     

Two maps on one surface

Two embeddings of a graph in a surface S are said to be “equivalent” if they are identical under an homeomorphism of S that is orientation‐preserving for orientable S. Two graphs cellularly embedded simultaneously in S are said to be “jointly embedded” if the only points of intersection involve an edge of one graph transversally crossing an edge of the other. The problem is to find equivalent embeddings of the two graphs that minimize the number of these edge‐crossings; this minimum we call the “joint crossing number” of the two graphs. In this paper, we calculate the exact value for the joint crossing number for two graphs simultaneously embedded in the projective plane. Furthermore, we give upper and lower bounds when the surface is the torus, which in many cases give an exact answer. In particular, we give a construction for re‐embedding (equivalently) the graphs in the torus so that the number of crossings is best possible up to a constant factor. Finally, we show that if one of the embeddings is replaced by its “mirror image,” then the joint crossing number can decrease, but not by more than 6.066%. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 198–216, 2001     

Fractional chromatic numbers of cones over graphs

We introduce a construction called the cone over a graph. It is a natural generalisation of Mycielski's construction. We give a formula for the fractional chromatic numbers of all cones over graphs, which generalizes that given in 3 for Mycielski's construction. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 87–94, 2001     

A characterization of P4‐indifference graphs

A graph is a P₄‐indifference graph if it admits a linear ordering ≺ on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has either a ≺ b ≺ c ≺ d or d ≺ c ≺ b ≺ a. P₄‐indifference graphs generalize indifference graphs and are perfectly orderable. We give a characterization of P₄‐indifference graphs by forbidden induced subgraphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 155‐162, 1999     

Counting 5‐connected planar triangulations

Let t_n be the number of rooted 5‐connected planar triangulations with 2n faces. We find t_n exactly for small n, as well as an asymptotic formula for n → ∞. Our results are found by compositions of lower connectivity maps whose faces are triangles or quadrangles. We also find the asymptotic number of cyclically 5‐edge connected cubic planar graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 18–35, 2001     

On triangles in ‐minor free graphs

We study graphs where each edge that is incident to a vertex of small degree (of degree at most 7 and 9, respectively) belongs to many triangles (at least 4 and 5, respectively) and show that these graphs contain a complete graph (K₆ and K₇, respectively) as a minor. The second case settles a problem of Nevo. Moreover, if each edge of a graph belongs to six triangles, then the graph contains a K₈‐minor or contains K_{2, 2, 2, 2, 2} as an induced subgraph. We then show applications of these structural properties to stress freeness and coloring of graphs. In particular, motivated by Hadwiger's conjecture, we prove that every K₇‐minor free graph is 8‐colorable and every K₈‐minor free graph is 10‐colorable.     

Forbidden minors for wye‐delta‐wye reducibility

A graph is Y Δ Y reducible if it can be reduced to a single vertex by a sequence of series‐parallel reductions and Y Δ Y transformations. The class of Y Δ Y reducible graphs is minor closed. We found a large number of minor minimal Y Δ Y irreducible graphs: a family of 57578 31‐edge graphs and another 40‐edge graph. It is still an open problem to characterize Y Δ Y reducible graphs in terms of a finite set of forbidden minors. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 317–321, 2004     

Genus polynomials and crosscap‐number polynomials for ring‐like graphs

An H‐linear graph is obtained by transforming a collection of copies of a fixed graph H into a chain. An H‐ring‐like graph is formed by binding the two end‐copies of H in such a chain to each other. Genus polynomials have been calculated for bindings of several kinds. In this paper, we substantially generalize the rules for constructing sequences of H‐ring‐like graphs from sequences of H‐linear graphs, and we give a general method for obtaining a recursion for the genus polynomials of the graphs in a sequence of ring‐like graphs. We use Chebyshev polynomials to obtain explicit formulas for the genus polynomials of several such sequences. We also give methods for obtaining recursions for partial genus polynomials and for crosscap‐number polynomials of a bar‐ring of a sequence of disjoint graphs.     

A characterization of some graph classes using excluded minors

In this article we present a structural characterization of graphs without K ₅ and the octahedron as a minor. We introduce semiplanar graphs as arbitrary sums of planar graphs, and give their characterization in terms of excluded minors. Some other excluded minor theorems for 3-connected minors are shown. Communicated by Attila Pethő     

Cubic graphs without cut‐vertices having the same path layer matrix

The path layer matrix (or path degree sequence) of a graph G contains quantitative information about all possible paths in G. The entry (i,j) of this matrix is the number of paths in G having initial vertex i and length j. It is known that there are cubic graphs on 62 vertices having the same path layer matrix (A. A. Dobrynin. J Graph Theory 17 (1993) 1–4). A new upper bound of 36 vertices for the least order of such cubic graphs is established. This bound is realized by cubic graphs without cut‐vertices. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 177–182, 2001     

Planar graphs: Random walks and bipartiteness testing

We initiates the study of property testing in arbitrary planar graphs. We prove that bipartiteness can be tested in constant time, improving on the previous bound of for graphs on n vertices. The constant‐time testability was only known for planar graphs with bounded degree. Our algorithm is based on random walks. Since planar graphs have good separators, that is, bad expansion, our analysis diverges from standard techniques that involve the fast convergence of random walks on expanders. We reduce the problem to the task of detecting an odd‐parity cycle in a multigraph induced by constant‐length cycles. We iteratively reduce the length of cycles while preserving the detection probability, until the multigraph collapses to a collection of easily discoverable self‐loops. Our approach extends to arbitrary minor‐free graphs. We also believe that our techniques will find applications to testing other properties in arbitrary minor‐free graphs.     

Planar graph colorings without short monochromatic cycles

It is well known that every planar graph G is 2‐colorable in such a way that no 3‐cycle of G is monochromatic. In this paper, we prove that G has a 2‐coloring such that no cycle of length 3 or 4 is monochromatic. The complete graph K₅ does not admit such a coloring. On the other hand, we extend the result to K₅‐minor‐free graphs. There are planar graphs with the property that each of their 2‐colorings has a monochromatic cycle of length 3, 4, or 5. In this sense, our result is best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 25–38, 2004     

On Switching to H‐Free Graphs

In this article, we study the problem of deciding if, for a fixed graph H, a given graph is switching equivalent to an H‐free graph. Polynomial‐time algorithms are known for H having at most three vertices or isomorphic to P₄. We show that for H isomorphic to a claw, the problem is polynomial, too. On the other hand, we give infinitely many graphs H such that the problem is NP‐complete, thus solving an open problem [Kratochvíl, Ne?et?il and Zýka, Ann Discrete Math 51 (1992)]. Further, we give a characterization of graphs switching equivalent to a K_{1, 2}‐free graph by ten forbidden‐induced subgraphs, each having five vertices. We also give the forbidden‐induced subgraphs for graphs switching equivalent to a forest of bounded vertex degrees.     

Locally s‐distance transitive graphs

We give a unified approach to analyzing, for each positive integer s, a class of finite connected graphs that contains all the distance transitive graphs as well as the locally s‐arc transitive graphs of diameter at least s. A graph is in the class if it is connected and if, for each vertex v, the subgroup of automorphisms fixing v acts transitively on the set of vertices at distance i from v, for each i from 1 to s. We prove that this class is closed under forming normal quotients. Several graphs in the class are designated as degenerate, and a nondegenerate graph in the class is called basic if all its nontrivial normal quotients are degenerate. We prove that, for s≥2, a nondegenerate, nonbasic graph in the class is either a complete multipartite graph or a normal cover of a basic graph. We prove further that, apart from the complete bipartite graphs, each basic graph admits a faithful quasiprimitive action on each of its (1 or 2) vertex‐orbits or a biquasiprimitive action. These results invite detailed additional analysis of the basic graphs using the theory of quasiprimitive permutation groups. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:176‐197, 2012     

On constructible graphs,locally Helly graphs,and convexity

A (finite or infinite) graph G is constructible if there exists a well‐ordering ≤ of its vertices such that for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Particular constructible graphs are Helly graphs and connected bridged graphs. In this paper we study a new class of constructible graphs, the class of locally Helly graphs. A graph G is locally Helly if, for every pair (x,y) of vertices of G whose distance is d ≥ 2, there exists a vertex whose distance to x is d ? 1 and which is adjacent to y and to all neighbors of y whose distance to x is at most d. Helly graphs are locally Helly, and the converse holds for finite graphs. Among different properties we prove that a locally Helly graph is strongly dismantable, hence cop‐win, if and only if it contains no isometric rays. We show that a locally Helly graph G is finitely Helly, that is, every finite family of pairwise non‐disjoint balls of G has a non‐empty intersection. We give a sufficient condition by forbidden subgraphs so that the three concepts of Helly graphs, of locally Helly graphs and of finitely Helly graphs are equivalent. Finally, generalizing different results, in particular those of Bandelt and Chepoi 1 about Helly graphs and bridged graphs, we prove that the Helly number h(G) of the geodesic convexity in a constructible graph G is equal to its clique number ω(G), provided that ω(G) is finite. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 280–298, 2003     

New Bounds on the Grundy Number of Products of Graphs

The Grundy number of a graph G is the largest k such that G has a greedy k‐coloring, that is, a coloring with k colors obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this article, we give new bounds on the Grundy number of the product of two graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:78–88, 2012     

Trading crossings for handles and crosscaps

Let c_k = cr_k (G) denote the minimum number of edge crossings when a graph G is drawn on an orientable surface of genus k. The (orientable) crossing sequence c_o, c₁,c₂…encodes the trade‐off between adding handles and decreasing crossings. We focus on sequences of the type c_o > c₁ > c₂ = 0; equivalently, we study the planar and toroidal crossing number of doubly‐toroidal graphs. For every ? > 0 we construct graphs whose orientable crossing sequence satisfies c₁/c_o > 5/6??. In other words, we construct graphs where the addition of one handle can save roughly 1/6th of the crossings, but the addition of a second handle can save five times more crossings. We similarly define the non‐orientable crossing sequence ?₀,?₁,?₂, ··· for drawings on non‐orientable surfaces. We show that for every ?₀ > ?₁ > 0 there exists a graph with non‐orientable crossing sequence ?₀, ?₁, 0. We conjecture that every strictly‐decreasing sequence of non‐negative integers can be both an orientable crossing sequence and a non‐orientable crossing sequence (with different graphs). © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 230–243, 2001     

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.     

I‐graphs and the corresponding configurations

We consider the class of I‐graphs I(n,j,k), which is a generalization over the class of the generalized Petersen graphs. We study different properties of I‐graphs, such as connectedness, girth, and whether they are bipartite or vertex‐transitive. We give an efficient test for isomorphism of I‐graphs and characterize the automorphism groups of I‐graphs. Regular bipartite graphs with girth at least 6 can be considered as Levi graphs of some symmetric combinatorial configurations. We consider configurations that arise from bipartite I‐graphs. Some of them can be realized in the plane as cyclic astral configurations, i.e., as geometric configurations with maximal isometric symmetry. © 2005 Wiley Periodicals, Inc.