Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Entire DC Network
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 …
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 …