Circular colorings of edge‐weighted graphs

The notion of (circular) colorings of edge‐weighted graphs is introduced. This notion generalizes the notion of (circular) colorings of graphs, the channel assignment problem, and several other optimization problems. For instance, its restriction to colorings of weighted complete graphs corresponds to the traveling salesman problem (metric case). It also gives rise to a new definition of the chromatic number of directed graphs. Several basic results about the circular chromatic number of edge‐weighted graphs are derived. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 107–116, 2003     

Edge list multicoloring trees: An extension of Hall's theorem

We prove a necessary and sufficient condition for the existence of edge list multicoloring of trees. The result extends the Halmos–Vaughan generalization of Hall's theorem on the existence of distinct representatives of sets. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 246–255, 2003     

Minimally (k,k)‐edge‐connected graphs

For an integer l > 1, the l‐edge‐connectivity of a connected graph with at least l vertices is the smallest number of edges whose removal results in a graph with l components. A connected graph G is (k, l)‐edge‐connected if the l‐edge‐connectivity of G is at least k. In this paper, we present a structural characterization of minimally (k, k)‐edge‐connected graphs. As a result, former characterizations of minimally (2, 2)‐edge‐connected graphs in [J of Graph Theory 3 (1979), 15–22] are extended. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 116–131, 2003     

Nowhere‐zero 3‐flows in locally connected graphs

Let G be a graph. For each vertex v ∈V(G), N_v denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), N_v is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003     

On Edge-Colored Graphs Covered by Properly Colored Cycles

We characterize edge-colored graphs in which every edge belongs to some properly colored cycle. We obtain our result by applying a characterization of 1-extendable graphs. Received: April, 2003     

NP completeness of the edge precoloring extension problem on bipartite graphs

We show that the following problem is NP complete: Let G be a cubic bipartite graph and f be a precoloring of a subset of edges of G using at most three colors. Can f be extended to a proper edge 3‐coloring of the entire graph G? This result provides a natural counterpart to classical Holyer's result on edge 3‐colorability of cubic graphs and a strengthening of results on precoloring extension of perfect graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 156–160, 2003     

Degree sequence conditions for equal edge‐connectivity and minimum degree,depending on the clique number

Using the well‐known Theorem of Turán, we present in this paper degree sequence conditions for the equality of edge‐connectivity and minimum degree, depending on the clique number of a graph. Different examples will show that these conditions are best possible and independent of all the known results in this area. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 234–245, 2003     

Density of the circular chromatic numbers of series‐parallel graphs

In this paper we show that every simple cubic graph on n vertices has a set of at least ? n/4 ? disjoint 2‐edge paths and that this bound is sharp. Our proof provides a polynomial time algorithm for finding such a set in a simple cubic graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 57–79, 2003     

An algebraic characterization of projective‐planar graphs

We give a detailed algebraic characterization of when a graph G can be imbedded in the projective plane. The characterization is in terms of the existence of a dual graph G* on the same edge set as G, which satisfies algebraic conditions inspired by homology groups and intersection products in homology groups. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 320–331, 2003     

Short proofs of classical theorems

We give proofs of Ore's theorem on Hamilton circuits, Brooks' theorem on vertex coloring, and Vizing's theorem on edge coloring, as well as the Chvátal-Lovász theorem on semi-kernels, a theorem of Lu on spanning arborescences of tournaments, and a theorem of Gutin on diameters of orientations of graphs. These proofs, while not radically different from existing ones, are perhaps simpler and more natural. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 159–165, 2003     

Super Restricted Edge Connectivity of Regular Graphs

An edge cut of a connected graph is called restricted if it separates this graph into components each having order at least 2; a graph G is super restricted edge connected if G−S contains an isolated edge for every minimum restricted edge cut S of G. It is proved in this paper that k-regular connected graph G is super restricted edge connected if k > |V(G)|/2+1. The lower bound on k is exemplified to be sharp to some extent. With this observation, we determined the number of edge cuts of size at most 2k−2 of these graphs. Supported by NNSF of China (10271105); Ministry of Science and Technology of Fujian (2003J036); Education Ministry of Fujian (JA03147)     

3‐colorability of 4‐regular hamiltonian graphs

On the model of the cycle‐plus‐triangles theorem, we consider the problem of 3‐colorability of those 4‐regular hamiltonian graphs for which the components of the edge‐complement of a given hamiltonian cycle are non‐selfcrossing cycles of constant length ≥ 4. We show that this problem is NP‐complete. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 125–140, 2003     

On removable cycles through every edge

Mader and Jackson independently proved that every 2‐connected simple graph G with minimum degree at least four has a removable cycle, that is, a cycle C such that G/E(C) is 2‐connected. This paper considers the problem of determining when every edge of a 2‐connected graph G, simple or not, can be guaranteed to lie in some removable cycle. The main result establishes that if every deletion of two edges from G remains 2‐connected, then, not only is every edge in a removable cycle but, for every two edges, there are edge‐disjoint removable cycles such that each contains one of the distinguished edges. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 155–164, 2003     

Vertex‐distinguishing edge colorings of graphs

We consider lower bounds on the the vertex‐distinguishing edge chromatic number of graphs and prove that these are compatible with a conjecture of Burris and Schelp 8 . We also find upper bounds on this number for certain regular graphs G of low degree and hence verify the conjecture for a reasonably large class of such graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 95–109, 2003     

Maximal sets of hamilton cycles in complete multipartite graphs

A set S of edge‐disjoint hamilton cycles in a graph G is said to be maximal if the edges in the hamilton cycles in S induce a subgraph H of G such that G ? E(H) contains no hamilton cycles. In this context, the spectrum S(G) of a graph G is the set of integers m such that G contains a maximal set of m edge‐disjoint hamilton cycles. This spectrum has previously been determined for all complete graphs and for all complete bipartite graphs. In this paper, we extend these results to the complete multipartite graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 49–66, 2003     

Two methods for the generation of chordal graphs

In this paper two methods for automatic generation of connected chordal graphs are proposed: the first one is based on new results concerning the dynamic maintenance of chordality under edge insertions; the second is based on expansion/merging of maximal cliques. Theoretical and experimental results are presented. In both methods, chordality is preserved along the whole generation process. L. Markenzon’s research is partially supported by grant 301068/2003-8, CNPq, Brazil.     

Highly edge‐connected detachments of graphs and digraphs

Let G = (V,E) be a graph or digraph and r : V → Z₊. An r‐detachment of G is a graph H obtained by ‘splitting’ each vertex ν ∈ V into r(ν) vertices. The vertices ν₁,…,ν_r(ν) obtained by splitting ν are called the pieces of ν in H. Every edge uν ∈ E corresponds to an edge of H connecting some piece of u to some piece of ν. Crispin Nash‐Williams 9 gave necessary and sufficient conditions for a graph to have a k‐edge‐connected r‐detachment. He also solved the version where the degrees of all the pieces are specified. In this paper, we solve the same problems for directed graphs. We also give a simple and self‐contained new proof for the undirected result. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 67–77, 2003     

The structure of saturated critical blocks

A 2‐connected graph G is a critical block if G ? v is not 2‐connected for every vertex v ∈ V(G). A critical block G is a saturated critical block if G + e is not a critical block for any new edge e. The structure of all saturated critical blocks and a procedure for constructing every saturated critical block are determined. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 223–237, 2003     

Graph homomorphisms through random walks

In this paper we introduce some general necessary conditions for the existence of graph homomorphisms, which hold in both directed and undirected cases. Our method is a combination of Diaconis and Saloff–Coste comparison technique for Markov chains and a generalization of Haemers interlacing theorem. As some applications, we obtain a necessary condition for the spanning subgraph problem, which also provides a generalization of a theorem of Mohar (1992) as a necessary condition for Hamiltonicity. In particular, in the case that the range is a Cayley graph or an edge‐transitive graph, we obtain theorems with a corollary about the existence of homomorphisms to cycles. This, specially, provides a proof of the fact that the Coxeter graph is a core. Also, we obtain some information about the cores of vertex‐transitive graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 15–38, 2003