Increasing Hamiltonian paths in random edge orderings

Let f be an edge ordering of K_n: a bijection . For an edge , we call f(e) the label of e. An increasing path in K_n is a simple path (visiting each vertex at most once) such that the label on each edge is greater than the label on the previous edge. We let S(f) be the number of edges in the longest increasing path. Chvátal and Komlós raised the question of estimating m(n): the minimum value of S(f) over all orderings f of K_n. The best known bounds on m(n) are , due respectively to Graham and Kleitman, and to Calderbank, Chung, and Sturtevant. Although the problem is natural, it has seen essentially no progress for three decades. In this paper, we consider the average case, when the ordering is chosen uniformly at random. We discover the surprising result that in the random setting, S(f) often takes its maximum possible value of n – 1 (visiting all of the vertices with an increasing Hamiltonian path). We prove that this occurs with probability at least about 1/ e. We also prove that with probability 1‐ o(1), there is an increasing path of length at least 0.85 n, suggesting that this Hamiltonian (or near‐Hamiltonian) phenomenon may hold asymptotically almost surely. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 588–611, 2016     

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     

Optimal acyclic edge‐coloring of cubic graphs

An acyclic edge‐coloring of a graph is a proper edge‐coloring such that the subgraph induced by the edges of any two colors is acyclic. The acyclic chromatic index of a graph G is the smallest number of colors in an acyclic edge‐coloring of G. We prove that the acyclic chromatic index of a connected cubic graph G is 4, unless G is K₄ or K_3,3; the acyclic chromatic index of K₄ and K_3,3 is 5. This result has previously been published by Fiam?ík, but his published proof was erroneous.     

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     

Eulerian subgraphs in 3‐edge‐connected graphs and Hamiltonian line graphs

In this paper, we show that if G is a 3‐edge‐connected graph with and , then either G has an Eulerian subgraph H such that , or G can be contracted to the Petersen graph in such a way that the preimage of each vertex of the Petersen graph contains at least one vertex in S. If G is a 3‐edge‐connected planar graph, then for any , G has an Eulerian subgraph H such that . As an application, we obtain a new result on Hamiltonian line graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 308–319, 2003     

Equitable edge‐colorings of simple graphs

An edge‐coloring of a graph G is equitable if, for each v∈V(G), the number of edges colored with any one color incident with v differs from the number of edges colored with any other color incident with v by at most one. A new sufficient condition for equitable edge‐colorings of simple graphs is obtained. This result covers the previous results, which are due to Hilton and de Werra, verifies a conjecture made by Hilton recently, and substantially extends it to a more general class of graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:175‐197, 2011     

Large components in r‐edge‐colorings of Kn have diameter at most five

Reflecting on problems posed by Gyárfás [Ramsey Theory Yesterday, Today and Tomorrow, Birkhäuser, Basel, 2010, pp. 77–96] and Mubayi [Electron J Combin 9 (2002), #R42], we show in this note that every r‐edge‐coloring of K_n contains a monochromatic component of diameter at most five on at least n/(r?1) vertices. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 337–340, 2012     

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     

Independent sets and 2‐factors in edge‐chromatic‐critical graphs

In 1968, Vizing made the following two conjectures for graphs which are critical with respect to the chromatic index: (1) every critical graph has a 2‐factor, and (2) every independent vertex set in a critical graph contains at most half of the vertices. We prove both conjectures for critical graphs with many edges, and determine upper bounds for the size of independent vertex sets in those graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 113–118, 2004     

Sparse pseudo‐random graphs are Hamiltonian

In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a d‐regular graph G on n vertices satisfies and n is large enough, then G is Hamiltonian. We also show how our main result can be used to prove that for every c >0 and large enough n a Cayley graph X (G,S), formed by choosing a set S of c log⁵ n random generators in a group G of order n, is almost surely Hamiltonian. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 17–33, 2003     

Multistrain edge‐based compartmental model on networks

Multistrain diseases, which are infected through individual contacts, pose severe public health threat nowadays. In this paper, we build competitive and mutative two‐strain edge‐based compartmental models using probability generation function (PGF) and pair approximation (PA). Both of them are ordinary differential equations. Their basic reproduction numbers and final size formulas are explicitly derived. We show that the formula gives a unique positive final epidemic size when the reproduction number is larger than unity. We further consider competitive and mutative multistrain diseases spreading models and compute their basic reproduction numbers. We perform numerical simulations that show some dynamical properties of the competitive and mutative two‐strain models.     

The complete bipartite graphs with a unique edge‐transitive embedding

Jones, Nedela, and Škoviera (2008) showed that a complete bipartite graph has a unique orientably regular embedding if and only if . In this article, we extend this result by proving that a complete bipartite graph has a unique orientably edge‐transitive embedding if and only if .     

The acyclic edge chromatic number of a random d‐regular graph is d + 1

We prove the theorem from the title: the acyclic edge chromatic number of a random d‐regular graph is asymptotically almost surely equal to d + 1. This improves a result of Alon, Sudakov, and Zaks and presents further support for a conjecture that Δ(G) + 2 is the bound for the acyclic edge chromatic number of any graph G. It also represents an analog of a result of Robinson and the second author on edge chromatic number. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 69–74, 2005     

A Sufficient Condition for Edge Chromatic Critical Graphs to Be Hamiltonian—An Approach to Vizing's 2‐Factor Conjecture

In this article, we consider Vizing's 2‐Factor Conjecture which claims that any Δ‐critical graph has a 2‐factor, and show that if G is a Δ‐critical graph with n vertices satisfying , then G is Hamiltonian and thus G has a 2‐factor. Meanwhile in this article, we also consider long cycles of overfull critical graphs and obtain that if G is an overfull Δ‐critical graph with n vertices, then the circumference of G is at least min.© 2012 Wiley Periodicals, Inc. J. Graph Theory 00: 1‐14, 2012     

The edge‐bandwidth of theta graphs

An edge‐labeling f of a graph G is an injection from E(G) to the set of integers. The edge‐bandwidth of G is B′(G) = min_f {B′(f)} where B′(f) is the maximum difference between labels of incident edges of G. The theta graph Θ(l₁,…,l_m) is the graph consisting of m pairwise internally disjoint paths with common endpoints and lengths l₁ ≤ ··· ≤ l_m. We determine the edge‐bandwidth of all theta graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 89–98, 2000     

Odd 4‐edge‐colorability of graphs

An odd k‐edge‐coloring of a graph G is a (not necessarily proper) edge‐coloring with at most k colors such that each nonempty color class induces a graph in which every vertex is of odd degree. Pyber (1991) showed that every simple graph is odd 4‐edge‐colorable, and Lužar et al. (2015) showed that connected loopless graphs are odd 5‐edge‐colorable, with one particular exception that is odd 6‐edge‐colorable. In this article, we prove that connected loopless graphs are odd 4‐edge‐colorable, with two particular exceptions that are respectively odd 5‐ and odd 6‐edge‐colorable. Moreover, a color class can be reduced to a size at most 2.     

The independence number of an edge‐chromatic critical graph

A graph G with maximum degree Δ and edge chromatic number χ′(G)>Δ is edge‐Δ‐critical if χ′(G?e)=Δ for every edge e of G. It is proved here that the vertex independence number of an edge‐Δ‐critical graph of order n is less than . For large Δ, this improves on the best bound previously known, which was roughly ; the bound conjectured by Vizing, which would be best possible, is . © 2010 Wiley Periodicals, Inc. J Graph Theory 66:98‐103, 2011     

Facial non‐repetitive edge‐coloring of plane graphs

A sequence r₁, r₂, …, r_2n such that r_i=r_{n+ i} for all 1≤i≤n is called a repetition. A sequence S is called non‐repetitive if no block (i.e. subsequence of consecutive terms of S) is a repetition. Let G be a graph whose edges are colored. A trail is called non‐repetitive if the sequence of colors of its edges is non‐repetitive. If G is a plane graph, a facial non‐repetitive edge‐coloring of G is an edge‐coloring such that any facial trail (i.e. a trail of consecutive edges on the boundary walk of a face) is non‐repetitive. We denote π′_f(G) the minimum number of colors of a facial non‐repetitive edge‐coloring of G. In this article, we show that π′_f(G)≤8 for any plane graph G. We also get better upper bounds for π′_f(G) in the cases when G is a tree, a plane triangulation, a simple 3‐connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound 4 for trees is tight. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 38–48, 2010     

Color degree and monochromatic degree conditions for short properly colored cycles in edge‐colored graphs

For an edge‐colored graph, its minimum color degree is defined as the minimum number of colors appearing on the edges incident to a vertex and its maximum monochromatic degree is defined as the maximum number of edges incident to a vertex with a same color. A cycle is called properly colored if every two of its adjacent edges have distinct colors. In this article, we first give a minimum color degree condition for the existence of properly colored cycles, then obtain the minimum color degree condition for an edge‐colored complete graph to contain properly colored triangles. Afterwards, we characterize the structure of an edge‐colored complete bipartite graph without containing properly colored cycles of length 4 and give the minimum color degree and maximum monochromatic degree conditions for an edge‐colored complete bipartite graph to contain properly colored cycles of length 4, and those passing through a given vertex or edge, respectively.