Subdivisions in Digraphs of Large Out-Degree or Large Dichromatic Number
- Others:
- Département d'informatique - ENS Paris (DI-ENS) ; École normale supérieure - Paris (ENS-PSL) ; Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
- Combinatorics, Optimization and Algorithms for Telecommunications (COATI) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED) ; Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
- Universidade Estadual de Campinas = University of Campinas (UNICAMP)
- Institut Universitaire de France (IUF) ; Ministère de l'Education nationale, de l'Enseignement supérieur et de la Recherche (M.E.N.E.S.R.)
- Modèles de calcul, Complexité, Combinatoire (MC2) ; Laboratoire de l'Informatique du Parallélisme (LIP) ; École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL) ; Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL) ; Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
Citation
Description
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.
Abstract
International audience
Additional details
- URL
- https://hal.archives-ouvertes.fr/hal-02275082
- URN
- urn:oai:HAL:hal-02275082v1
- Origin repository
- UNICA