Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 7 of 7
Full-Text Articles in Entire DC Network
Rainbow Matchings And Hamilton Cycles In Random Graphs, Deepak Bal, Alan Frieze
Rainbow Matchings And Hamilton Cycles In Random Graphs, Deepak Bal, Alan Frieze
Deepak Bal
Let HPn,m,k be drawn uniformly from all m-edge, k-uniform, k-partite hypergraphs where each part of the partition is a disjoint copy of [n]. We let HP(κ) n,m,k be an edge colored version, where we color each edge randomly from one of κ colors. We show that if κ = n and m = Kn log n where K is sufficiently large then w.h.p. there is a rainbow colored perfect matching. I.e. a perfect matching in which every edge has a different color. We also show that if n is even and m = Kn log n where K is sufficiently …
The T-Tone Chromatic Number Of Random Graphs, Deepak Bal, Patrick Bennett, Andrzej Dudek, Alan Frieze
The T-Tone Chromatic Number Of Random Graphs, Deepak Bal, Patrick Bennett, Andrzej Dudek, Alan Frieze
Deepak Bal
A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from ([k]2) such that adjacent vertices receive disjoint labels and vertices distance 2 apart receive distinct labels. The 2-tone chromatic number of a graph G, denoted τ 2(G) is the smallest k such thatG admits a proper 2-tone k coloring. In this paper, we prove that w.h.p. for p≥Cn−1/4ln9/4n,τ2(Gn,p)=(2+o(1))χ(Gn,p) where χ represents the ordinary chromatic number. For sparse random graphs with p = c/n, c constant, we prove that τ2(Gn,p)=⌈(8Δ+1−−−−−−√+5)/2 where Δ represents the maximum degree. For …
A Greedy Algorithm For Finding A Large 2-Matching On A Random Cubic Graph, Deepak Bal, Patrick Bennett, Tom Bohman, Alan Frieze
A Greedy Algorithm For Finding A Large 2-Matching On A Random Cubic Graph, Deepak Bal, Patrick Bennett, Tom Bohman, Alan Frieze
Deepak Bal
A 2-matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2-matching U is the number of edges in U and this is at least $n-\k(U)$ where n is the number of vertices of G and $\k$ denotes the number of components. In this paper, we analyze the performance of a greedy algorithm \textsc{2greedy} for finding a large 2-matching on a random 3-regular graph. We prove that with high probability, the algorithm outputs a 2-matching U with$\k(U) = \tilde{\Theta}\of{n^{1/5}}$.
Power Of K Choices And Rainbow Spanning Trees In Random Graphs, Deepak Bal, Patrick Bennett, Alan Frieze, Pawel Pralat
Power Of K Choices And Rainbow Spanning Trees In Random Graphs, Deepak Bal, Patrick Bennett, Alan Frieze, Pawel Pralat
Deepak Bal
We consider the Erdős-Rényi random graph process, which is a stochastic process that starts with nvertices and no edges, and at each step adds one new edge chosen uniformly at random from the set of missing edges. Let G(n,m) be a graph with m edges obtained after m steps of this process. Each edge ei (i=1,2,…,m) of G(n,m) independently chooses precisely k∈N colours, uniformly at random, from a given set of n−1 colours (one may view ei as a multi-edge). We stop the process prematurely at time M when the following two events hold: G(n,M) is connected and every colour …
Packing Tree Factors In Random And Pseudo-Random Graphs, Deepak Bal, Alan Frieze, Michael Krivelevich, Po-Shen Loh
Packing Tree Factors In Random And Pseudo-Random Graphs, Deepak Bal, Alan Frieze, Michael Krivelevich, Po-Shen Loh
Deepak Bal
For a fixed graph H with t vertices, an H-factor of a graph G with n vertices, where t divides n, is a collection of vertex disjoint (not necessarily induced) copies of H in G covering all vertices of G. We prove that for a fixed tree T on t vertices and ϵ>0, the random graph Gn,p, with n a multiple of t, with high probability contains a family of edge-disjoint T-factors covering all but an ϵ-fraction of its edges, as long as ϵ4np≫log2n. Assuming stronger divisibility conditions, the edge probability can be taken down to p>Clognn. A …
Rainbow Arborescence In Random Digraphs, Deepak Bal, Patrick Bennett, Colin Cooper, Alan Frieze, Pawel Pralat
Rainbow Arborescence In Random Digraphs, Deepak Bal, Patrick Bennett, Colin Cooper, Alan Frieze, Pawel Pralat
Deepak Bal
We consider the Erd˝os-R´enyi random directed graph process, which is a stochastic process that starts with n vertices and no edges, and at each step adds one new directed edge chosen uniformly at random from the set of missing edges. Let D(n, m) be a graph with m edges obtained after m steps of this process. Each edge ei (i = 1, 2, . . . , m) of D(n, m) independently chooses a colour, taken uniformly at random from a given set of n(1 + O(log log n/ log n)) = n(1 + o(1)) colours. We stop the process …
Packing Tight Hamilton Cycles In Uniform Hypergraphs, Deepak Bal, Alan Frieze
Packing Tight Hamilton Cycles In Uniform Hypergraphs, Deepak Bal, Alan Frieze
Deepak Bal
We say that a k-uniform hypergraph C is a Hamilton cycle of type ℓ, for some 1 ≤ ℓ ≤ k, if there exists a cyclic ordering of the vertices of C such that every edge consists of k consecutive vertices and for every pair of consecutive edges Ei−1, Ei in C (in the natural ordering of the edges) we have |Ei−1 \ Ei | = ℓ. We define a class of (ε, p)-regular hypergraphs, that includes random hypergraphs, for which we can prove the existence of a decomposition of almost all edges into type ℓ Hamilton cycles, where ℓ < k/2.