Search

For any r ≥ 2 and k ≥ 3, the r-color size-Ramsey number R(G,r) of a k-uniform hypergraph G is the smallest integer m such that there exists a k-uniform hypergraph H on m edges such that any coloring of the edges of H with r colors yields a monochromatic copy of G. Let Pn,k-1 (k) denote the k-uniform tight path on n vertices. Dudek et al. [J. Graph Theory, 86 (2017), pp. 104-121] showed that the size-Ramsey number of tight paths R(Pn,k-1 (k), 2) = O(nk-1-α(logn)1+α) where α = (k-2)/2k-1 +1. In this paper, we improve their bound by showing that R(Pn,k-1(k), r) = O(rk(nlogn)k/2) for all k ≥ 3 and r ≥ 2. [ABSTRACT FROM AUTHOR]

Consider a directed analogue of the random graph process on n vertices, where the n(n - 1) edges are ordered uniformly at random and revealed one at a time. It is known that with high probability (w.h.p.) the first digraph in this process with both in-degree and out-degree ≥ q has a q-edge-coloring with a Hamilton cycle in each color. We show that this coloring can be constructed online, where each edge must be irrevocably colored as soon as it appears. In a similar fashion, for the undirected random graph process, we present an online n-edge-coloring algorithm which yields w.h.p. q disjoint rainbow Hamilton cycles in the first graph containing q disjoint Hamilton cycles. [ABSTRACT FROM AUTHOR]

In this paper, we give the following result: If D is a digraph of order n, and if d+ D(u)+d D(v) n for every two distinct vertices u and v with (u; v) =2 A(D), then D has a directed 2-factor with exactly k directed cycles of length at least 3, where n 12k+3. This result is equivalent to the following result: If G is a balanced bipartite graph of order 2n with partite sets X and Y , and if dG(x) + dG(y) n + 2 for every two vertices x 2 X and y 2 Y with xy =2 E(G), then for every perfect matching M, G has a 2-factor with exactly k cycles of length at least 6 containing every edge of M, where n 12k + 3. These results are generalizations of theorems concerning Hamilton cycles due to Woodall [Proc. Lond. Math. Soc., 24 (1972), pp. 739{755] and Las Vergnas [Problemes de couplages et problemes hamiltoniens en theorie des graphes, Ph.D. thesis, University of Paris, 1972], respectively. [ABSTRACT FROM AUTHOR]

Let L be a set of positive integers. We call a (directed) graph G an L-cycle graph if all cycle lengths in G belong to L. Let c(L; n) be the maximum number of cycles possible in an n-vertex L-cycle graph (we use ~c(L; n) for the number of cycles in directed graphs). In the undirected case we show that for any fixed set L, we have c(L; n) = (nbk=`c), where k is the largest element of L and 2` is the smallest even element of L (if L contains only odd elements, then c(L; n) = (n) holds). We also give a characterization of L-cycle graphs when L is a single element. In the directed case we prove that for any fixed set L, we have ~c(L; n) = (1 + o(1))( n 1 k 1 ) k 1, where k is the largest element of L. We determine the exact value of ~c(fkg; n) for every k and characterize all graphs attaining this maximum. [ABSTRACT FROM AUTHOR]

Let G be an n-node simple directed planar graph with nonnegative edge weights. We study the fundamental problems of computing (1) a global cut of G with minimum weight and (2) a cycle of G with minimum weight. The best previously known algorithm for the former problem, running in O(n log³ n) time, can be obtained from the algorithm of Łącki, Nussbaum, Sankowski, and Wulff-Nilsen for single-source all-sinks maximum flows. The best previously known result for the latter problem is the O(n log³ n)-time algorithm of Wulff-Nilsen. By exploiting duality between the two problems in planar graphs, we solve both problems in O(n log n log log n) time via a divideand-conquer algorithm that finds a shortest nondegenerate cycle. The kernel of our result is an O(n log log n)-time algorithm for computing noncrossing shortest paths among nodes well ordered on a common face of a directed plane graph, which is extended from the algorithm of Italiano, Nussbaum, Sankowski, and Wulff-Nilsen for an undirected plane graph. [ABSTRACT FROM AUTHOR]