|
| | | | |
| | | |
| Stat |
Members: 3644
Articles: 2'497'992
Articles rated: 2609
16 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Subdivisions in digraphs of large out-degree or large dichromatic number | | Pierre Aboulker
; Nathann Cohen
; Fréderic Havet
; William Lochet
; Phablo F. S. Moura
; Stéphan Thomassé
; | | Date: |
4 Oct 2016 | | Abstract: | In 1985, Mader conjectured the existence of a function $f$ such that every
digraph with minimum out-degree at least $f(k)$ contains a subdivision of the
transitive tournament of order $k$. This conjecture is still completely open,
as the existence of $f(5)$ remains unknown. In this paper, we show that if $D$
is an oriented path, or an in-arborescence (i.e., a tree with all edges
oriented towards the root) or the union of two directed paths from $x$ to $y$
and a directed path from $y$ to $x$, then every digraph with minimum out-degree
large enough contains a subdivision of $D$. Additionally, we study Mader’s
conjecture considering another graph parameter. The dichromatic number of a
digraph $D$ is the smallest integer $k$ such that $D$ can be partitioned into
$k$ acyclic subdigraphs. We show that any digraph with dichromatic number
greater than $4^m (n-1)$ contains every digraph with $n$ vertices and $m$ arcs
as a subdivision. | | Source: | arXiv, 1610.0876 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER