2021/02/25 by Louis DeBiasio, DeBiasio, Louis, András Gyárfás +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2102.12794
openalex publication_date 2021/02/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A digraph is \em d-dominating if every set of at most d vertices has a common out-neighbor. For all integers d≥ 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 d≥ 2, proving 4≤ f(2)≤ 8 and 2d≤ f(d)≤ 2d(\fracdd-1d-1) for all d≥ 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-Erdő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.