Two graphs without planar covers

In this note we prove that two specific graphs do not have finite planar covers. The graphs are K₇–C₄ and K_4,5–4K₂. This research is related to Negami's 1‐2‐∞ Conjecture which states “A graph G has a finite planar cover if and only if it embeds in the projective plane.” In particular, Negami's Conjecture reduces to showing that 103 specific graphs do not have finite planar covers. Previous (and subsequent) work has reduced these 103 to a few specific graphs. This paper covers 2 of the remaining cases. The sole case currently remaining is to show that K_2,2,2,1 has no finite planar cover. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 318–326, 2002     

Another two graphs with no planar covers

A graph H is a cover of a graph G if there exists a mapping φ from V( H ) onto V( G ) such that φ maps the neighbors of every vertex υ in H bijectively to the neighbors of φ(υ) in G . Negami conjectured in 1986 that a connected graph has a finite planar cover if and only if it embeds in the projective plane. It follows from the results of Archdeacon, Fellows, Negami, and the author that the conjecture holds as long as K _1,2,2,2 has no finite planar cover. However, this is still an open question, and K _1,2,2,2 is not the only minor‐minimal graph in doubt. Let ??₄ (?₂) denote the graph obtained from K _1,2,2,2 by replacing two vertex‐disjoint triangles (four edge‐disjoint triangles) not incident with the vertex of degree 6 with cubic vertices. We prove that the graphs ??₄ and ?₂ have no planar covers. This fact is used in [P. Hlin?ný, R. Thomas, On possible counterexamples to Negami's planar cover conjecture, 1999 (submitted)] to show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 227–242, 2001     

K4,4 − e has no finite planar cover

A graph G has a planar cover if there exists a planar graph H , and a homomorphism φ : H → G that maps the neighbors of each vertex bijectively. Each graph that has an embedding in the projective plane also has a finite planar cover. Negami conjectured the converse in 1988. This conjecture holds as long as no minor-minimal nonprojective graph has a finite planar cover. From the list there remain only two cases not solved yet—the graphs K _4,4 − e and K _1,2,2,2. We prove the nonexistence of a finite planar cover of K _4,4 − e. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 51–60, 1998     

Prism‐hamiltonicity of triangulations

The prism over a graph G is the Cartesian product G □ K₂ of G with the complete graph K₂. If the prism over G is hamiltonian, we say that G is prism‐hamiltonian. We prove that triangulations of the plane, projective plane, torus, and Klein bottle are prism‐hamiltonian. We additionally show that every 4‐connected triangulation of a surface with sufficiently large representativity is prism‐hamiltonian, and that every 3‐connected planar bipartite graph is prism‐hamiltonian. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 181–197, 2008     

Toroidal graphs containing neither nor 6‐cycles are 4‐choosable

The choosability of a graph G is the minimum k such that having k colors available at each vertex guarantees a proper coloring. Given a toroidal graph G, it is known that , and if and only if G contains K₇. Cai et al. (J Graph Theory 65(1) (2010), 1–15) proved that a toroidal graph G without 7‐cycles is 6‐choosable, and if and only if G contains K₆. They also proved that a toroidal graph G without 6‐cycles is 5‐choosable, and conjectured that if and only if G contains K₅. We disprove this conjecture by constructing an infinite family of non‐4‐colorable toroidal graphs with neither K₅ nor cycles of length at least 6; moreover, this family of graphs is embeddable on every surface except the plane and the projective plane. Instead, we prove the following slightly weaker statement suggested by Zhu: toroidal graphs containing neither (a K₅ missing one edge) nor 6‐cycles are 4‐choosable. This is sharp in the sense that forbidding only one of the two structures does not ensure that the graph is 4‐choosable.     

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     

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 possible counterexamples to Negami's planar cover conjecture

A simple graph H is a cover of a graph G if there exists a mapping φ from H onto G such that φ maps the neighbors of every vertex υ in H bijectively to the neighbors of φ (υ) in G . Negami conjectured in 1986 that a connected graph has a finite planar cover if and only if it embeds in the projective plane. The conjecture is still open. It follows from the results of Archdeacon, Fellows, Negami, and the first author that the conjecture holds as long as the graph K _1,2,2,2 has no finite planar cover. However, those results seem to say little about counterexamples if the conjecture was not true. We show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. Moreover, we exhibit a finite list of sets of graphs such that the set of excluded minors for the property of having finite planar cover is one of the sets in our list. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 183–206, 2004     

Subdivisions of K5 in Graphs Embedded on Surfaces With Face‐Width at Least 5

We prove that if G is a 5‐connected graph embedded on a surface Σ (other than the sphere) with face‐width at least 5, then G contains a subdivision of K₅. This is a special case of a conjecture of P. Seymour, that every 5‐connected nonplanar graph contains a subdivision of K₅. Moreover, we prove that if G is 6‐connected and embedded with face‐width at least 5, then for every v ∈ V(G), G contains a subdivision of K₅ whose branch vertices are v and four neighbors of v.     

Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k

A graph G is (k,0)‐colorable if its vertices can be partitioned into subsets V₁ and V₂ such that in G[V₁] every vertex has degree at most k, while G[V₂] is edgeless. For every integer k?0, we prove that every graph with the maximum average degree smaller than (3k+4)/(k+2) is (k,0)‐colorable. In particular, it follows that every planar graph with girth at least 7 is (8, 0)‐colorable. On the other hand, we construct planar graphs with girth 6 that are not (k,0)‐colorable for arbitrarily large k. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:83–93, 2010     

NZ‐flows in strong products of graphs

We prove that the strong product G₁? G₂ of G₁ and G₂ is ?₃‐flow contractible if and only if G₁? G₂ is not T? K₂, where T is a tree (we call T? K₂ a K₄‐tree). It follows that G₁? G₂ admits an NZ 3 ‐flow unless G₁? G₂ is a K₄ ‐tree. We also give a constructive proof that yields a polynomial algorithm whose output is an NZ 3‐flow if G₁? G₂ is not a K₄ ‐tree, and an NZ 4‐flow otherwise. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 267–276, 2010     

Cycle‐minors and subdivisions of wheels

In this paper we prove two results. The first is an extension of a result of Dirac which says that any set of n vertices of an n‐connected graph lies in a cycle. We prove that if V′ is a set of at most 2n vertices in an n‐connected graph G, then G has, as a minor, a cycle using all of the vertices of V′. The second result says that if G is an n+1‐connected graph with maximum vertex degree Δ then G contains a subgraph that is a subdivision of W_2n if and only if Δ≥2n. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 100–108, 2009     

On the projectively almost-factorial varieties

Summary A projectively normal subvariety (X,O _X) ofP ^N(k), k an algebraically closed field of characteristic zero, will be said to be projectively almost-factorial if each Weil divisor has a multiple which is a complete intersection in X. The main result is the following: (X,O _X) is projectively almost-factorial if and only if for all x ∈ X the local ringO _x is almost-factorial and the quotient ofPic(X) modulo the subgroup generated by the class ofO _X (1) is torsion. We also prove the invariance of the projective almost-factoriality up to isomorphisms and state some relations between the projective almost-factoriality (resp. projective factoriality) of X and the almost-factoriality (resp. factoriality) of the affine open subvarieties. Finally we discuss some consequences of the main result in the case k=ℂ: in particular we prove that the Picard group of a projectively almost-factorial variety is isomorphic to the Néron-Severi group, hence finitely generated. Entrata in Redazione il 23 aprile 1976. AMS(MOS) subject classification (1970): Primary 14C20, 13F15.     

On the vertex face total chromatic number of planar graphs

Let G be a planar graph. The vertex face total chromatic number _χ13(G) of G is the least number of colors assigned to V(G)∪F(G) such that no adjacent or incident elements receive the same color. The main results of this paper are as follows: (1) We give the vertex face total chromatic number for all outerplanar graphs and modulus 3-regular maximal planar graphs. (2) We prove that if G is a maximal planar graph or a lower degree planar graph, i.e., ∠(G) ≤ 3, then _χ13(G) ≤ 6. © 1996 John Wiley & Sons, Inc.     

Hamilton cycles in 3‐out

Let G_3‐out denote the random graph on vertex set [n] in which each vertex chooses three neighbors uniformly at random. Note that G_3‐out has minimum degree 3 and average degree 6. We prove that the probability that G_3‐out is Hamiltonian goes to 1 as n tends to infinity. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Spanning 2‐trails from degree sum conditions

Suppose G is a simple connected n‐vertex graph. Let σ₃(G) denote the minimum degree sum of three independent vertices in G (which is ∞ if G has no set of three independent vertices). A 2‐trail is a trail that uses every vertex at most twice. Spanning 2‐trails generalize hamilton paths and cycles. We prove three main results. First, if σ₃G)≥ n ‐ 1, then G has a spanning 2‐trail, unless G ? K_1,3. Second, if σ₃(G) ≥ n, then G has either a hamilton path or a closed spanning 2‐trail. Third, if G is 2‐edge‐connected and σ₃(G) ≥ n, then G has a closed spanning 2‐trail, unless G ? K_2,3 or K (the 6‐vertex graph obtained from K_2,3 by subdividing one edge). All three results are sharp. These results are related to the study of connected and 2‐edge‐connected factors, spanning k‐walks, even factors, and supereulerian graphs. In particular, a closed spanning 2‐trail may be regarded as a connected (and 2‐edge‐connected) even [2,4]‐factor. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 298–319, 2004     

On the perfect orderability of unions of two graphs

A graph G is perfectly orderable, if it admits an order < on its vertices such that the sequential coloring algorithm delivers an optimum coloring on each induced subgraph (H, <) of (G, <). A graph is a threshold graph, if it contains no P₄, 2K₂, and C₄ as induced subgraph. A theorem of Chvátal, Hoàng, Mahadev, and de Werra states that a graph is perfectly orderable, if it is the union of two threshold graphs. In this article, we investigate possible generalizations of the above theorem. Hoàng has conjectured that, if G is the union of two graphs G₁ and G₂, then G is perfectly orderable whenever G₁ and G₂ are both P₄‐free and 2K₂‐free. We show that the complement of the chordless cycle with at least five vertices cannot be a counter‐example to this conjecture, and we prove a special case of it: if G₁ and G₂ are two edge‐disjoint graphs that are P₄‐free and 2K₂‐free, then the union of G₁ and G₂ is perfectly orderable. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 32–43, 2000     

Continuous k‐to‐1 functions between complete graphs whose orders are of a different parity

A function between graphs is k‐to‐1 if each point in the codomain has precisely k pre‐images in the domain. Given two graphs, G and H, and an integer k≥1, and considering G and H as subsets of ?³, there may or may not be a k‐to‐1 continuous function (i.e. a k‐to‐1 map in the usual topological sense) from G onto H. In this paper we consider graphs G and H whose order is of a different parity and determine the even and odd values of k for which there exists a k‐to‐1 map from G onto H. We first consider k‐to‐1 maps from K_2r onto K_2s+1 and prove that for 1≤r≤s, (r, s)≠(1, 1), there is a continuous k‐to‐1 map for k even if and only if k≥2s and for k odd if and only if k≥?s?_o (where ?s?_o indicates the next odd integer greater than or equal to s). We then consider k‐to‐1 maps from K_2s+1 onto K_2s. We show that for 1≤r<s, such a map exists for even values of k if and only if k≥2s. We also prove that whatever the values of r and s are, no such k‐to‐1 map exists for odd values of k. To conclude, we give all triples (n, k, m) for which there is a k‐to‐1 map from K_n onto K_m in the case when n≤m. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 35–60, 2010.     

Free <Emphasis Type="Italic">G</Emphasis>-spaces and maximal equivariant compactifications

For a compact Lie group G we prove that every free (resp., semifree) G-space admits a based-free (resp., semifree) G-compactification. Examples of finite- and infinite-dimensional G-spaces are presented that do not admit a free or based-free G-compactification. We give several characterizations of the maximal G-compactification β_GX that are further applied to prove the formula (β_GX)/H=β_G/H(X/H) for arbitrary closed normal subgroup H⊂G. Mathematics Subject Classification (2000) 54H15, 54D35     

Proof of a tiling conjecture of Komlós

A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n‐vertex graph of minimum degree at least (1 ? (1/χ_cr(H)))n, where χ_cr(H) denotes the critical chromatic number of H, then G contains an H‐matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180–205, 2003