Cycle double covers and spanning minors II

In this paper we continue our investigations from [R. Häggkvist, K. Markström, Cycle double covers and spanning minors, Technical Report 07, Department of Mathematics, Umeå University, Sweden, 2001, J. Combin. Theory, Ser. B, to appear] regarding spanning subgraphs which imply the existence of cycle double covers. We prove that if a cubic graph G has a spanning subgraph isomorphic to a subdivision of a bridgeless cubic graph on at most 10 vertices then G has a CDC. A notable result is thus that a cubic graph with a spanning Petersen minor has a CDC, a result also obtained by Goddyn [L. Goddyn, Cycle covers of graphs, Ph.D. Thesis, University of Waterloo, 1988].     

Splits of circuits

This paper discusses an attempt at identifying a property of circuits in (nonplanar) graphs resembling the separation property of circuits in planar graphs derived from the Jordan Curve Theorem.If G is a graph and C is a circuit in G, we say that two circuits in G form a split of C if the symmetric difference of their edges sets is equal to the edge set of C, and if they are separated in G by the intersection of their vertex sets.García Moreno and Jensen, A note on semiextensions of stable circuits, Discrete Math. 309 (2009) 4952-4954, asked whether such a split exists for any circuit C whenever G is 3-connected. We observe that if true, this implies a strong form of a version of the Cycle Double-Cover Conjecture suggested in the Ph.D. thesis of Luis Goddyn. The main result of the paper shows that the property holds for Hamilton circuits in cubic graphs.     

Characterization of edge‐colored complete graphs with properly colored Hamilton paths

An edge‐colored graph H is properly colored if no two adjacent edges of H have the same color. In 1997, J. Bang‐Jensen and G. Gutin conjectured that an edge‐colored complete graph G has a properly colored Hamilton path if and only if G has a spanning subgraph consisting of a properly colored path C₀ and a (possibly empty) collection of properly colored cycles C₁,C₂,…, C_d such that provided . We prove this conjecture. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 333–346, 2006     

Even subgraphs of bridgeless graphs and 2-factors of line graphs

By Petersen's theorem, a bridgeless cubic multigraph has a 2-factor. Fleischner generalised this result to bridgeless multigraphs of minimum degree at least three by showing that every such multigraph has a spanning even subgraph. Our main result is that every bridgeless simple graph with minimum degree at least three has a spanning even subgraph in which every component has at least four vertices. We deduce that if G is a simple bridgeless graph with n vertices and minimum degree at least three, then its line graph has a 2-factor with at most max{1,(3n-4)/10} components. This upper bound is best possible.     

Long cycles and spanning subgraphs of locally maximal 1-planar graphs

A graph is 1-planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1-planar. For a 3-connected locally maximal 1-planar graph G, we show the existence of a spanning 3-connected planar subgraph and prove that G is Hamiltonian if G has at most three 3-vertex-cuts, and that G is traceable if G has at most four 3-vertex-cuts. Moreover, infinitely many nontraceable 5-connected 1-planar graphs are presented.     

Transformations of edge-colourings of cubic graphs

In this paper we shall study and describe all possible forms of the so-called change-graph which is the subgraph of a cubic graph G containing all the edges (and only the edges) having different colours in two different edge-colourings of G.     

The Ramsey number of a graph with bounded maximum degree

The Ramsey number of a graph G is the least number t for which it is true that whenever the edges of the complete graph on t vertices are colored in an arbitrary fashion using two colors, say red and blue, then it is always the case that either the red subgraph contains G or the blue subgraph contains G. A conjecture of P. Erdös and S. Burr is settled in the affirmative by proving that for each d ≥ 1, there exists a constant c so that if G is any graph on n vertices with maximum degree d, then the Ramsey number of G is at most cn.     

Chromatic number of sparse colored mixed planar graphs

A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph G is defined as the smallest order of a colored mixed graph H such that there exists a (arc-color preserving) homomorphism from G to H. We study in this paper the colored mixed chromatic number of planar graphs, partial 2-trees and outerplanar graphs with given girth.     

Heterochromatic tree partition numbers for complete bipartite graphs

An r-edge-coloring of a graph G is a surjective assignment of r colors to the edges of G. A heterochromatic tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by t_r(G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we give an explicit formula for the heterochromatic tree partition number of an r-edge-colored complete bipartite graph K_m,n.     

Minimal 2-matching-covered graphs

A perfect 2-matching M of a graph G is a spanning subgraph of G such that each component of M is either an edge or a cycle. A graph G is said to be 2-matching-covered if every edge of G lies in some perfect 2-matching of G. A 2-matching-covered graph is equivalent to a “regularizable” graph, which was introduced and studied by Berge. A Tutte-type characterization for 2-matching-covered graph was given by Berge. A 2-matching-covered graph is minimal if G−e is not 2-matching-covered for all edges e of G. We use Berge’s theorem to prove that the minimum degree of a minimal 2-matching-covered graph other than K₂ and K₄ is 2 and to prove that a minimal 2-matching-covered graph other than K₄ cannot contain a complete subgraph with at least 4 vertices.     

A reduction criterion for supereulerian graphs

Let G be a graph, and let H be a connected subgraph of G. When it is known that the graph G/H (obtained from G by contracting H to a vertex) has a spanning eulerian subgraph, under what conditions can it be inferred that G itself has a spanning eulerian subgraph? © 1996 John Wiley & Sons, Inc.     

Spanning Cyclic Subdivisions of Vertex-Disjoint Cycles and Chorded Cycles in Graphs

Let G be a graph on n ≥ 3 vertices and H be a subgraph of G such that each component of H is a cycle with at most one chord. In this paper we prove that if the minimum degree of G is at least n/2, then G contains a spanning subdivision of H such that only non-chord edges of H are subdivided. This gives a new generalization of the classical result of Dirac on the existence of Hamilton cycles in graphs.     

The bipartite edge frustration of composite graphs

The smallest number of edges that have to be deleted from a graph to obtain a bipartite spanning subgraph is called the bipartite edge frustration of G and denoted by φ(G). In this paper we determine the bipartite edge frustration of some classes of composite graphs.     

Rainbow faces in edge‐colored plane graphs

A face of an edge‐colored plane graph is called rainbow if the number of colors used on its edges is equal to its size. The maximum number of colors used in an edge coloring of a connected plane graph Gwith no rainbow face is called the edge‐rainbowness of G. In this paper we prove that the edge‐rainbowness of Gequals the maximum number of edges of a connected bridge face factor H of G, where a bridge face factor H of a plane graph Gis a spanning subgraph H of Gin which every face is incident with a bridge and the interior of any one face f∈F(G) is a subset of the interior of some face f′∈F(H). We also show upper and lower bounds on the edge‐rainbowness of graphs based on edge connectivity, girth of the dual graphs, and other basic graph invariants. Moreover, we present infinite classes of graphs where these equalities are attained. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 84–99, 2009     

Edge-colorings of cubic graphs with elements of point-transitive Steiner triple systems

A cubic graph G is S-edge-colorable for a Steiner triple system S if its edges can be colored with points of S in such a way that the points assigned to three edges sharing a vertex form a triple in S. We show that a cubic graph is S-edge-colorable for every non-trivial affine Steiner triple system S unless it contains a well-defined obstacle called a bipartite end. In addition, we show that all cubic graphs are S-edge-colorable for every non-projective non-affine point-transitive Steiner triple system S.     

Extending an edge-coloring

When can a k-edge-coloring of a subgraph K of a graph G be extended to a k-edge-coloring of G? One necessary condition is that for all X ? E(G) - E(K), where μ_i(X) is the maximum cardinality of a subset of X whose union with the set of edges of K colored i is a matching. This condition is not sufficient in general, but is sufficient for graphs of very simple structure. We try to locate the border where sufficiency ends.     

Brick partitions of graphs

For each rational number q=b/c where b≥c are positive integers, we define a q-brick of G to be a maximal subgraph H of G such that cH has b edge-disjoint spanning trees, and a q-superbrick of G to be a maximal subgraph H of G such that cH−e has b edge-disjoint spanning trees for all edges e of cH, where cH denotes the graph obtained from H by replacing each edge by c parallel edges. We show that the vertex sets of the q-bricks of G partition the vertex set of G, and that the vertex sets of the q-superbricks of G form a refinement of this partition. The special cases when q=1 are the partitions given by the connected components and the 2-edge-connected components of G, respectively. We obtain structural results on these partitions and describe their relationship to the principal partitions of a matroid.     

A Necessary and Sufficient Condition for the Existence of a Heterochromatic Spanning Tree in a Graph

We prove the following theorem. An edge-colored (not necessary to be proper) connected graph G of order n has a heterochromatic spanning tree if and only if for any r colors (1≤r≤n−2), the removal of all the edges colored with these r colors from G results in a graph having at most r+1 components, where a heterochromatic spanning tree is a spanning tree whose edges have distinct colors.     

Fractional perfect b-matching polytopes I: General theory

The fractional perfect b-matching polytope of an undirected graph G is the polytope of all assignments of nonnegative real numbers to the edges of G such that the sum of the numbers over all edges incident to any vertex v   is a prescribed nonnegative number _bv$b_v$. General theorems which provide conditions for nonemptiness, give a formula for the dimension, and characterize the vertices, edges and face lattices of such polytopes are obtained. Many of these results are expressed in terms of certain spanning subgraphs of G which are associated with subsets or elements of the polytope. For example, it is shown that an element u of the fractional perfect b-matching polytope of G is a vertex of the polytope if and only if each component of the graph of u either is acyclic or else contains exactly one cycle with that cycle having odd length, where the graph of u is defined to be the spanning subgraph of G whose edges are those at which u is positive.     

On Petersen's graph theorem

In this paper we prove the following: let G be a graph with e_G edges, which is (k ? 1)-edge- connected, and with all valences ?k. Let 1?r?k be an integer, then G contains a spanning subgraph H, so that all valences in H are ?r, with no more than ?re_G?k? edges. The proof is based on a useful extension of Tutte's factor theorem [4,5], due to Lovász [3]. For other extensions of Petersen's theorem, see [6,7,8].