Search

Given an n vertex graph whose edges have colored from one of τ colors C = {ci, C2,..., cr}, we define the Hamilton cycle color profile hcp(G) to be the set of vectors (mi, m2,..., mr) ∈ [0, n}r such that there exists a Hamilton cycle that is the concatenation of τ paths Pi, P2, ∙.., Pr, where Pi contains rΠι edges of color cι. We study hcp(Gn p) when the edges are randomly colored. We discuss the profile close to the threshold for the existence of a Hamilton cycle and the threshold for when ∕icp(Gnjf>) = {(mι, m2,..., mr) ∈ [0,n]r: mi + m2 + ∙ ∙ ∙ + mr = n}. [ABSTRACT FROM AUTHOR]

We consider the existence of patterned Hamilton cycles in randomly colored random graphs. Given a string π over a set of colors { 1, 2, . . . , r}, we say that a Hamilton cycle is π -colored if the pattern repeats at intervals of length |π| as we go around the cycle. We prove a hitting time result for the existence of such a cycle. We also prove a hitting time result for the related notion of π -connected. [ABSTRACT FROM AUTHOR]

For given simple graphs G1 and G2, the size Ramsey number Ȓ(G1,G2) is the smallest positive integer m, where there exists a graph G with m edges such that in any edge coloring of G with two colors red and blue, there is either a red copy of G1 or a blue copy of G2. In 1981, Erdös and Faudree investigated the size Ramsey number Ȓ(Kn, tK2), where Kn is a complete graph on n vertices and tK2 is a matching of size t. They obtained the value of Ȓ(Kn, tK2) when n ≥ 4t-1 as well as for t = 2 and asked for the behavior of these numbers when t is much larger than n. In this regard, they posed the following interesting question: For every positive integer n, is it true that ... In this paper, we obtain the exact value of Ȓ(Kn, tK2) for every pair of positive integers n, t, and as a byproduct, we give an affirmative answer to the question of Erdös and Faudree. [ABSTRACT FROM AUTHOR]

We first consider the following problem. We are given a fixed perfect matching M of [n] and we add random edges one at a time until there is a Hamilton cycle containing M. We show that with high probability (w.h.p.) the hitting time for this event is the same as that for the first time there are no isolated vertices in the graph induced by the random edges. We then use this result for the following problem. We generate random edges and randomly color them black or white. A path/cycle is said to be zebraic if the colors alternate along the path. We show that w.h.p. the hitting time for a zebraic Hamilton cycle coincides with every vertex meeting at least one edge of each color. We then consider some related problems and (partially) extend our results to multiple colors. We also briefly consider directed versions. [ABSTRACT FROM AUTHOR]

Gyárfás, Győri, and Simonovits [J. Comb., 7 (2016), pp. 205{216] proved that if a 3-uniform hypergraph with n vertices has no linear cycles, then its independence number α ≥ 2n/5. The hypergraph consisting of vertex disjoint copies of a complete hypergraph K3/5 on five vertices shows that equality can hold. They asked whether this bound can be improved if we exclude K3/5 as a subhypergraph and whether such a hypergraph is 2-colorable. In this paper, we answer these questions affirmatively. Namely, we prove that if a 3-uniform linear-cycle-free hypergraph doesn't contain K3 5 as a subhypergraph, then it is 2-colorable. This result clearly implies that its independence number α ≥ [n/2]. We show that this bound is sharp. Gyárfás, Gy}ori, and Simonovits also proved that a linear-cycle-free 3-uniform hypergraph contains a vertex of strong degree at most 2. In this context, we show that a linear-cycle-free 3-uniform hypergraph has a vertex of degree at most n - 2 when n ≥ 10. [ABSTRACT FROM AUTHOR]

In this paper we determine the chromatic number of graphs with two odd cycle lengths. Let G be a graph and L(G) be the set of all odd cycle lengths of G. We prove that (1) if L(G) = f3; 3 + 2lg, where l ≥ 2, then x(G) = maxf3; !(G)g, and (2) if L(G) = fk; k + 2lg, where k ≥ 5 and l ≥ 1, then x(G) = 3. These, together with the case L(G) = f3; 5g solved in [S.-S. Wang, SIAM J. Discrete Math., 22 (2008), pp. 1040{1072] give a complete solution to the general problem addressed in [S.-S. Wang, SIAM J. Discrete Math., 22 (2008), pp. 1040{1072; S.-M. Camacho and I. Schiermeyer, Discrete Math., 309 (2009), pp. 4916{4919; and T. Kaiser, O. Rucký, and R. Škrekovski, SIAM J. Discrete Math., 25 (2011), pp. 1069{1088]. Our results also improve a classical theorem of Gyárfás which asserts that x (G) ≤ 2jL(G)j + 2 for any graph G. [ABSTRACT FROM AUTHOR]