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     

Projective‐Planar Graphs with no K3, 4‐Minor. II

The authors previously published an iterative process to generate a class of projective‐planar K_{3, 4}‐free graphs called “patch graphs.” They also showed that any simple, almost 4‐connected, nonplanar, and projective‐planar graph that is K_{3, 4}‐free is a subgraph of a patch graph. In this article, we describe a simpler and more natural class of cubic K_{3, 4}‐free projective‐planar graphs that we call Möbius hyperladders. Furthermore, every simple, almost 4‐connected, nonplanar, and projective‐planar graph that is K_{3, 4}‐free is a minor of a Möbius hyperladder. As applications of these structures we determine the page number of patch graphs and of Möbius hyperladders.     

On total 9‐coloring planar graphs of maximum degree seven

Given a graph G, a total k‐coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If Δ(G) is the maximum degree of G, then no graph has a total Δ‐coloring, but Vizing conjectured that every graph has a total (Δ + 2)‐coloring. This Total Coloring Conjecture remains open even for planar graphs. This article proves one of the two remaining planar cases, showing that every planar (and projective) graph with Δ ≤ 7 has a total 9‐coloring by means of the discharging method. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 67–73, 1999     

A characterization of Zm‐well‐covered graphs of girth 6 or more

The class of Z_m‐well‐covered graphs, those in which the cardinality of every maximal independent subset of vertices is congruent to the same number modulo m, contains the well‐covered graphs as well as parity graphs. Here we consider such graphs, where there is no small cycle present and obtain a characterization for those of girth 6 or more. Weighted well‐covered graphs of girth 7 or more are also characterized, and this result is used, in turn, to characterize magic well‐covered graphs of girth 7 or more. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 246–255, 2000     

Projective‐Planar Graphs with No K3, 4‐Minor

An exact structure is described to classify the projective‐planar graphs that do not contain a K_{3, 4}‐minor. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

Obstruction sets for outer‐cylindrical graphs

A graph is outer‐cylindrical if it embeds in the sphere so that there are two distinct faces whose boundaries together contain all the vertices. The class of outer‐cylindrical graphs is closed under minors. We give the complete set of 38 minor‐minimal non‐outer‐cylindrical graphs, or equivalently, an excluded minor characterization of outer‐cylindrical graphs. We also give the obstruction sets under the related topological ordering and Y Δ‐ordering. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 42–64, 2001     

The geometry of t‐spreads in k‐walk‐regular graphs

A graph is walk‐regular if the number of closed walks of length ? rooted at a given vertex is a constant through all the vertices for all ?. For a walk‐regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d‐spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three‐dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k‐walk‐regular graphs, a family which includes both walk‐regular and distance‐regular graphs, and their t‐spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory 64:312–322, 2010     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

Planar graphs without 4‐cycles adjacent to 3‐cycles are list vertex 2‐arborable

It is known that not all planar graphs are 4‐choosable; neither all of them are vertex 2‐arborable. However, planar graphs without 4‐cycles and even those without 4‐cycles adjacent to 3‐cycles are known to be 4‐choosable. We extend this last result in terms of covering the vertices of a graph by induced subgraphs of variable degeneracy. In particular, we prove that every planar graph without 4‐cycles adjacent to 3‐cycles can be covered by two induced forests. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 234–240, 2009     

On the structure of clique‐free graphs

Using a clever inductive counting argument Erd?s, Kleitman and Rothschild showed in 1976 that almost all triangle‐free graphs are bipartite, i.e., that the cardinality of the two graph classes is asymptotically equal. In this paper we investigate the structure of the “few” triangle‐free graphs which are not bipartite. As it turns out, with high probability, these graphs are bipartite up to a few vertices. More precisely, almost all of them can be made bipartite by removing just one vertex. Almost all others can be made bipartite by removing two vertices, and then three vertices and so on. We also show that similar results hold if we replace “triangle‐free” by K_??+1‐free and “bipartite” by ??‐partite. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 37–53, 2001     

Average‐case complexity of shortest‐paths problems in the vertex‐potential model

We study the average‐case complexity of shortest‐paths problems in the vertex‐potential model. The vertex‐potential model is a family of probability distributions on complete directed graphs with arbitrary real edge lengths, but without negative cycles. We show that on a graph with n vertices and with respect to this model, the single‐source shortest‐paths problem can be solved in O(n²) expected time, and the all‐pairs shortest‐paths problem can be solved in O(n² log n) expected time. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 33–46, 2000     

Extending the disjoint‐representatives theorems of Hall,Halmos, and Vaughan to list‐multicolorings of graphs

Philip Hall's famous theorem on systems of distinct representatives and its not‐so‐famous improvement by Halmos and Vaughan (1950) can be regarded as statements about the existence of proper list‐colorings or list‐multicolorings of complete graphs. The necessary and sufficient condition for a proper “coloring” in these theorems has a rather natural generalization to a condition we call Hall's condition on a simple graph G, a vertex list assignment to G, and an assignment of nonnegative integers to the vertices of G. Hall's condition turns out to be necessary for the existence of a proper multicoloring of G under these assignments. The Hall‐Halmos‐Vaughan theorem may be stated: when G is a clique, Hall's condition is sufficient for the existence of a proper multicoloring. In this article, we undertake the study of the class HHV of simple graphs G for which Hall's condition is sufficient for the existence of a proper multicoloring. It is shown that HHV is contained in the class ℋ︁₀ of graphs in which every block is a clique and each cut‐vertex lies in exactly two blocks. On the other hand, besides cliques, the only connected graphs we know to be in HHV are (i) any two cliques joined at a cut‐vertex, (ii) paths, and (iii) the two connected graphs of order 5 in ℋ︁₀, which are neither cliques, paths, nor two cliques stuck together. In case (ii), we address the constructive aspect, the problem of deciding if there is a proper coloring and, if there is, of finding one. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 199–219, 2000     

Injective colorings of planar graphs with few colors

An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. In this paper some results on injective colorings of planar graphs with few colors are presented. We show that all planar graphs of girth ≥ 19 and maximum degree Δ are injectively Δ-colorable. We also show that all planar graphs of girth ≥ 10 are injectively (Δ+1)-colorable, that Δ+4 colors are sufficient for planar graphs of girth ≥ 5 if Δ is large enough, and that subcubic planar graphs of girth ≥ 7 are injectively 5-colorable.     

Mapping Planar Graphs into Projective Cubes

Projective cubes are obtained by identifying antipodal vertices of hypercubes. We introduce a general problem of mapping planar graphs into projective cubes. This question, surprisingly, captures several well‐known theorems and conjectures in the theory of planar graphs. As a special case , we prove that the Clebsch graph, a triangle‐free graph on 16 vertices, is the smallest triangle‐free graph to which every triangle‐free planar graph admits a homomorphism.     

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.     

Clique‐coloring some classes of odd‐hole‐free graphs

We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K₄‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006     

Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs

Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.     

Complexity of clique‐coloring odd‐hole‐free graphs

In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, but on the other hand it is NP‐hard to decide if they are 2‐clique‐colorable, and we do not know if there exists any bound k₀ such that they are all k₀ ‐clique‐colorable. First we will prove that (odd hole, codiamond)‐free graphs are 2‐clique‐colorable. Then we will demonstrate that the complexity of 2‐clique‐coloring odd‐hole‐free graphs is actually Σ₂ P‐complete. Finally we will study the complexity of deciding whether or not a graph and all its subgraphs are 2‐clique‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 139–156, 2009     

A characterization of weakly four‐connected graphs

A graph G = (V, E) is called weakly four‐connected if G is 4‐edge‐connected and G ? x is 2‐edge‐connected for all x ∈ V. We give sufficient conditions for the existence of ‘splittable’ vertices of degree four in weakly four‐connected graphs. By using these results we prove that every minimally weakly four‐connected graph on at least four vertices contains at least three ‘splittable’ vertices of degree four, which gives rise to an inductive construction of weakly four‐connected graphs. Our results can also be applied in the problem of finding 2‐connected orientations of graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 217–229, 2006     

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.