DeBiasio, Louis and Gyárfás, András (2022) Covering 2-colored complete digraphs by monochromatic d-dominating digraphs. JOURNAL OF GRAPH THEORY, 100 (4). pp. 721-726. ISSN 0364-9024
|
Text
2102_12794v1.pdf Download (171kB) | Preview |
Abstract
A digraph is (Formula presented.) -dominating if every set of at most (Formula presented.) vertices has a common out-neighbor. For all integers (Formula presented.), let (Formula presented.) 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 (Formula presented.) monochromatic (Formula presented.) -dominating subgraphs. Note that the existence of (Formula presented.) is not obvious – indeed, the question which motivated this paper was simply to determine whether (Formula presented.) is bounded, even for (Formula presented.). We answer this question affirmatively for all (Formula presented.), proving (Formula presented.) and (Formula presented.). 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 (Formula presented.) -degenerate graphs. Moreover, a special case of our result is related to properties of (Formula presented.) -paradoxical tournaments. © 2022 Wiley Periodicals LLC.
| Item Type: | Article |
|---|---|
| Additional Information: | Export Date: 28 February 2023 CODEN: JGTHD Correspondence Address: DeBiasio, L.; Department of Mathematics, United States; email: debiasld@miamioh.edu Funding details: National Science Foundation, NSF, DMS‐1954170 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, K132696 Funding text 1: This research was supported in part by NSF grant DMS‐1954170 and in part by NKFIH Grant No. K132696. |
| Uncontrolled Keywords: | PROPERTY; Ramsey numbers; Directed graphs; Two-color; Subgraphs; Ramsey; infinite digraphs; degenerate graphs; Monochromatics; Complete digraph; monochromatic cover; paradoxical tournaments; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 17 Mar 2023 08:27 |
| Last Modified: | 06 Apr 2023 14:23 |
| URI: | http://real.mtak.hu/id/eprint/162331 |
Actions (login required)
 |
Edit Item |
