Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA note on colour-bias Hamilton cycles in dense graphs
93
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Balogh, Csaba, Jing and Pluhar recently determined the minimum degree threshold that ensures a $2$-coloured graph $G$ contains a Hamilton cycle of significant colour bias (i.e., a Hamilton cycle that contains significantly more than half of its edges in one colour). In this short note we extend this result, determining the corresponding threshold for $r$-colourings.
rate research
Read More
Given an $n$-vertex graph $G$ with minimum degree at least $d n$ for some fixed $d > 0$, the distribution $G cup mathbb{G}(n,p)$ over the supergraphs of $G$ is referred to as a (random) {sl perturbation} of $G$. We consider the distribution of edge-coloured graphs arising from assigning each edge of the random perturbation $G cup mathbb{G}(n,p)$ a colour, chosen independently and uniformly at random from a set of colours of size $r := r(n)$. We prove that such edge-coloured graph distributions a.a.s. admit rainbow Hamilton cycles whenever the edge-density of the random perturbation satisfies $p := p(n) geq C/n$, for some fixed $C > 0$, and $r = (1 + o(1))n$. The number of colours used is clearly asymptotically best possible. In particular, this improves upon a recent result of Anastos and Frieze (2019) in this regard. As an intermediate result, which may be of independent interest, we prove that randomly edge-coloured sparse pseudo-random graphs a.a.s. admit an almost spanning rainbow path.
Given an $n$ vertex graph whose edges have colored from one of $r$ colors $C={c_1,c_2,ldots,c_r}$, we define the Hamilton cycle color profile $hcp(G)$ to be the set of vectors $(m_1,m_2,ldots,m_r)in [0,n]^r$ such that there exists a Hamilton cycle that is the concatenation of $r$ paths $P_1,P_2,ldots,P_r$, where $P_i$ contains $m_i$ edges. We study $hcp(G_{n,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 $hcp(G_{n,p})={(m_1,m_2,ldots,m_r)in [0,n]^r:m_1+m_2+cdots+m_r=n}$.
We study the appearance of powers of Hamilton cycles in pseudorandom graphs, using the following comparatively weak pseudorandomness notion. A graph $G$ is $(varepsilon,p,k,ell)$-pseudorandom if for all disjoint $X$ and $Ysubset V(G)$ with $|X|gevarepsilon p^kn$ and $|Y|gevarepsilon p^ell n$ we have $e(X,Y)=(1pmvarepsilon)p|X||Y|$. We prove that for all $beta>0$ there is an $varepsilon>0$ such that an $(varepsilon,p,1,2)$-pseudorandom graph on $n$ vertices with minimum degree at least $beta pn$ contains the square of a Hamilton cycle. In particular, this implies that $(n,d,lambda)$-graphs with $lambdall d^{5/2 }n^{-3/2}$ contain the square of a Hamilton cycle, and thus a triangle factor if $n$ is a multiple of $3$. This improves on a result of Krivelevich, Sudakov and Szabo [Triangle factors in sparse pseudo-random graphs, Combinatorica 24 (2004), no. 3, 403--426]. We also extend our result to higher powers of Hamilton cycles and establish corresponding counti
Let $G$ be a graph of order $n$ with an edge-coloring $c$, and let $delta^c(G)$ denote the minimum color degree of $G$. A subgraph $F$ of $G$ is called rainbow if all edges of $F$ have pairwise distinct colors. There have been a lot results on rainbow cycles of edge-colored graphs. In this paper, we show that (i) if $delta^c(G)>frac{3n-3}{4}$, then every vertex of $G$ is contained in a rainbow triangle; (ii) $delta^c(G)>frac{3n}{4}$, then every vertex of $G$ is contained in a rainbow $C_4$; and (iii) if $G$ is complete, $ngeq 8k-18$ and $delta^c(G)>frac{n-1}{2}+k$, then $G$ contains a rainbow cycle of length at least $k$. Some gaps in previous publications are also found and corrected.
We prove that the number of Hamilton cycles in the random graph G(n,p) is n!p^n(1+o(1))^n a.a.s., provided that pgeq (ln n+ln ln n+omega(1))/n. Furthermore, we prove the hitting-time version of this statement, showing that in the random graph process, the edge that creates a graph of minimum degree 2 creates (ln n/e)^n(1+o(1))^n Hamilton cycles a.a.s.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
