Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProper vertex-pancyclicity of edge-colored complete graphs without joint monochromatic triangles
68
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In an edge-colored graph $(G,c)$, let $d^c(v)$ denote the number of colors on the edges incident with a vertex $v$ of $G$ and $delta^c(G)$ denote the minimum value of $d^c(v)$ over all vertices $vin V(G)$. A cycle of $(G,c)$ is called proper if any two adjacent edges of the cycle have distinct colors. An edge-colored graph $(G,c)$ on $ngeq 3$ vertices is called properly vertex-pancyclic if each vertex of $(G,c)$ is contained in a proper cycle of length $ell$ for every $ell$ with $3 le ell le n$. Fujita and Magnant conjectured that every edge-colored complete graph on $ngeq 3$ vertices with $delta^c(G)geq frac{n+1}{2}$ is properly vertex-pancyclic. Chen, Huang and Yuan partially solve this conjecture by adding an extra condition that $(G,c)$ does not contain any monochromatic triangle. In this paper, we show that this conjecture is true if the edge-colored complete graph contain no joint monochromatic triangles.
rate research
Read More
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 any two edges of $F$ have distinct colors. There have been a lot results in the existing literature on rainbow triangles in edge-colored complete graphs. Fujita and Magnant showed that for an edge-colored complete graph $G$ of order $n$, if $delta^c(G)geq frac{n+1}{2}$, then every vertex of $G$ is contained in a rainbow triangle. In this paper, we show that if $delta^c(G)geq frac{n+k}{2}$, then every vertex of $G$ is contained in at least $k$ rainbow triangles, which can be seen as a generalization of their result. Li showed that for an edge-colored graph $G$ of order $n$, if $delta^c(G)geq frac{n+1}{2}$, then $G$ contains a rainbow triangle. We show that if $G$ is complete and $delta^c(G)geq frac{n}{2}$, then $G$ contains a rainbow triangle and the bound is sharp. Hu et al. showed that for an edge-colored graph $G$ of order $ngeq 20$, if $delta^c(G)geq frac{n+2}{2}$, then $G$ contains two vertex-disjoint rainbow triangles. We show that if $G$ is complete with order $ngeq 8$ and $delta^c(G)geq frac{n+1}{2}$, then $G$ contains two vertex-disjoint rainbow triangles. Moreover, we improve the result of Hu et al. from $ngeq 20$ to $ngeq 7$, the best possible.
It is conjectured that every edge-colored complete graph $G$ on $n$ vertices satisfying $Delta^{mon}(G)leq n-3k+1$ contains $k$ vertex-disjoint properly edge-colored cycles. We confirm this conjecture for $k=2$, prove several additional weaker results for general $k$, and we establish structural properties of possible minimum counterexamples to the conjecture. We also reveal a close relationship between properly edge-colored cycles in edge-colored complete graphs and directed cycles in multi-partite tournaments. Using this relationship and our results on edge-colored complete graphs, we obtain several partial solutions to a conjecture on disjoint cycles in directed graphs due to Bermond and Thomassen.
The monochromatic tree partition number of an $r$-edge-colored graph $G$, denoted by $t_r(G)$, is the minimum integer $k$ such that whenever the edges of $G$ are colored with $r$ colors, the vertices of $G$ can be covered by at most $k$ vertex-disjoint monochromatic trees. In general, to determine this number is very difficult. For 2-edge-colored complete multipartite graph, Kaneko, Kano, and Suzuki gave the exact value of $t_2(K(n_1,n_2,...,n_k))$. In this paper, we prove that if $ngeq 3$, and K(n,n) is 3-edge-colored such that every vertex has color degree 3, then $t_3(K(n,n))=3.$
A digraph is {em $d$-dominating} if every set of at most $d$ vertices has a common out-neighbor. For all integers $dgeq 2$, let $f(d)$ be the smallest integer such that the vertices of every 2-edge-colored (finite or infinite) complete digraph (including loops) can be covered by the vertices of at most $f(d)$ monochromatic $d$-dominating subgraphs. Note that the existence of $f(d)$ is not obvious -- indeed, the question which motivated this paper was simply to determine whether $f(d)$ is bounded, even for $d=2$. We answer this question affirmatively for all $dgeq 2$, proving $4leq f(2)le 8$ and $2dleq f(d)le 2dleft(frac{d^{d}-1}{d-1}right)$ for all $dge 3$. We also give an example to show that there is no analogous bound for more than two colors. Our result provides a positive answer to a question regarding an infinite analogue of the Burr-ErdH{o}s conjecture on the Ramsey numbers of $d$-degenerate graphs. Moreover, a special case of our result is related to properties of $d$-paradoxical tournaments.
Properly colored cycles in edge-colored graphs are closely related to directed cycles in oriented graphs. As an analogy of the well-known Caccetta-H{a}ggkvist Conjecture, we study the existence of properly colored cycles of bounded length in an edge-colored graph. We first prove that for all integers $s$ and $t$ with $tgeq sgeq2$, every edge-colored graph $G$ with no properly colored $K_{s,t}$ contains a spanning subgraph $H$ which admits an orientation $D$ such that every directed cycle in $D$ is a properly colored cycle in $G$. Using this result, we show that for $rgeq4$, if the Caccetta-H{a}ggkvist Conjecture holds , then every edge-colored graph of order $n$ with minimum color degree at least $n/r+2sqrt{n}+1$ contains a properly colored cycle of length at most $r$. In addition, we also obtain an asymptotically tight total color degree condition which ensures a properly colored (or rainbow) $K_{s,t}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
