Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCovering 2-colored complete digraphs by monochromatic $d$-dominating digraphs
347
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Kostochka and Thomason independently showed that any graph with average degree $Omega(rsqrt{log r})$ contains a $K_r$ minor. In particular, any graph with chromatic number $Omega(rsqrt{log r})$ contains a $K_r$ minor, a partial result towards Hadwigers famous conjecture. In this paper, we investigate analogues of these results in the directed setting. There are several ways to define a minor in a digraph. One natural way is as follows. A strong $overrightarrow{K}_r$ minor is a digraph whose vertex set is partitioned into $r$ parts such that each part induces a strongly-connected subdigraph, and there is at least one edge in each direction between any two distinct parts. We investigate bounds on the dichromatic number and minimum out-degree of a digraph that force the existence of strong $overrightarrow{K}_r$ minors as subdigraphs. In particular, we show that any tournament with dichromatic number at least $2r$ contains a strong $overrightarrow{K}_r$ minor, and any tournament with minimum out-degree $Omega(rsqrt{log r})$ also contains a strong $overrightarrow{K}_r$ minor. The latter result is tight up to the implied constant, and may be viewed as a strong-minor analogue to the classical result of Kostochka and Thomason. Lastly, we show that there is no function $f: mathbb{N} rightarrow mathbb{N}$ such that any digraph with minimum out-degree at least $f(r)$ contains a strong $overrightarrow{K}_r$ minor, but such a function exists when considering dichromatic number.
We prove a conjecture of Fox, Huang, and Lee that characterizes directed graphs that have constant density in all tournaments: they are disjoint unions of trees that are each constructed in a certain recursive way.
Ramanujan graphs have fascinating properties and history. In this paper we explore a parallel notion of Ramanujan digraphs, collecting relevant results from old and recent papers, and proving some new ones. Almost-normal Ramanujan digraphs are shown to be of special interest, as they are extreme in the sense of an Alon-Boppana theorem, and they have remarkable combinatorial features, such as small diameter, Chernoff bound for sampling, optimal covering time and sharp cutoff. Other topics explored are the connection to Cayley graphs and digraphs, the spectral radius of universal covers, Alons conjecture for random digraphs, and explicit constructions of almost-normal Ramanujan digraphs.
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.
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.$
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
