Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

Subdivisions in dicritical digraphs with large order or digirth

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
  • معلومة اضافية
    • Contributors:
      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)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S); Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA); ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019); ANR-17-EURE-0004,UCA DS4H,UCA Systèmes Numériques pour l'Homme(2017)
    • بيانات النشر:
      HAL CCSD
      Elsevier
    • الموضوع:
      2024
    • Collection:
      HAL Université Côte d'Azur
    • نبذة مختصرة :
      International audience ; Aboulker et al. proved that a digraph with large enough dichromatic number contains any fixed digraph as a subdivision. The dichromatic number of a digraph is the smallest order of a partition of its vertex set into acyclic induced subdigraphs. A digraph is dicritical if the removal of any arc or vertex decreases its dichromatic number. In this paper we give sufficient conditions on a dicritical digraph of large order or large directed girth to contain a given digraph as a subdivision. In particular, we prove that (i) for every integers $k,\ell$, large enough dicritical digraphs with dichromatic number $k$ contain an orientation of a cycle with at least $\ell$ vertices; (ii) there are functions $f,g$ such that for every subdivision $F^*$ of a digraph $F$, digraphs with directed girth at least $f(F^*)$ and dichromatic number at least $g(F)$ contain a subdivision of $F^*$, and if $F$ is a tree, then $g(F)=|V(F)|$; (iii) there is a function $f$ such that for every subdivision $F^*$ of $TT_3$ (the transitive tournament on three vertices), digraphs with directed girth at least $f(F^*)$ and minimum out-degree at least $2$ contain $F^*$ as a subdivision.
    • Relation:
      info:eu-repo/semantics/altIdentifier/arxiv/2401.05938; ARXIV: 2401.05938
    • الرقم المعرف:
      10.1016/j.ejc.2024.104022
    • الدخول الالكتروني :
      https://inria.hal.science/hal-04471653
      https://inria.hal.science/hal-04471653v1/document
      https://inria.hal.science/hal-04471653v1/file/2401.05938.pdf
      https://doi.org/10.1016/j.ejc.2024.104022
    • Rights:
      http://creativecommons.org/licenses/by/ ; info:eu-repo/semantics/OpenAccess
    • الرقم المعرف:
      edsbas.8FB7E7E6