Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.00829 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913182318067712 |
|---|---|
| author | Sadhukhan, Arpan |
| author_facet | Sadhukhan, Arpan |
| contents | The dichromatic number $χ(\vec{G})$ of a digraph $\vec{G}$ is the minimum number of colors needed to color the vertices $V(\vec{G})$ in such a way that no monochromatic directed cycle is obtained. In this note, for any $k\in \mathbb{N}$, we give a simple construction of tournaments with dichromatic number exactly equal to $k$. The proofs are based on a combinatorial lemma on partitioning a checkerboard which may be of independent interest. We also generalize our finite construction to give an elementary construction of a complete digraph of cardinality equal to the cardinality of $\mathbb{R}$ and having an uncountable dichromatic number. Furthermore, we also construct an oriented balanced complete $n$-partite graph $\vec{K}^{(m)}_n$, such that the minimum number of colors needed to color its vertices such that there is no monochromatic directed triangle is greater than or equal to $nm/(n+2m-2)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_00829 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Simple Construction of Tournaments with Finite and Uncountable Dichromatic Number Sadhukhan, Arpan Combinatorics 05C20, 05C15, 05C63 The dichromatic number $χ(\vec{G})$ of a digraph $\vec{G}$ is the minimum number of colors needed to color the vertices $V(\vec{G})$ in such a way that no monochromatic directed cycle is obtained. In this note, for any $k\in \mathbb{N}$, we give a simple construction of tournaments with dichromatic number exactly equal to $k$. The proofs are based on a combinatorial lemma on partitioning a checkerboard which may be of independent interest. We also generalize our finite construction to give an elementary construction of a complete digraph of cardinality equal to the cardinality of $\mathbb{R}$ and having an uncountable dichromatic number. Furthermore, we also construct an oriented balanced complete $n$-partite graph $\vec{K}^{(m)}_n$, such that the minimum number of colors needed to color its vertices such that there is no monochromatic directed triangle is greater than or equal to $nm/(n+2m-2)$. |
| title | A Simple Construction of Tournaments with Finite and Uncountable Dichromatic Number |
| topic | Combinatorics 05C20, 05C15, 05C63 |
| url | https://arxiv.org/abs/2401.00829 |