Subdivisions in digraphs of large out-degree or large dichromatic number
type: Item
instance of: scholarly article
title: Subdivisions in digraphs of large out-degree or large dichromatic number
zbMATH Open document ID: 1417.05083
author: Pierre Aboulker
author: Nathann Cohen
author: William Lochet
author: Phablo F. S. Moura
author: Frédéric Havet
author: Stéphan Thomassé
published in: The Electronic Journal of Combinatorics
publication date: 2019-08-05T00:00:00Z
full work available at URL: https://arxiv.org/abs/1610.00876
full work available at URL: v26i3p19
review text: Summary: \textit{W. Mader} [Combinatorica 5, 161--165 (1985; Zbl 0576.05044)] 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. 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.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 7088645
MaRDI profile type: Publication
arXiv ID: 1610.00876
cites work: Oriented trees in digraphs
cites work: Disjoint directed cycles
cites work: Cycles in digraphs– a survey
cites work: Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
cites work: The Erdös-Sós conjecture for graphs of girth 5
cites work: Q3900086
cites work: Antidirected Subtrees of Directed Graphs
cites work: Subdivisions of oriented cycles in digraphs with large chromatic number
cites work: Immersing complete digraphs
cites work: In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
cites work: Q5509547
cites work: Short proof of Menger's theorem
cites work: Tree embeddings
cites work: The Directed Grid Theorem
cites work: Topological cliques in graphs II
cites work: Homomorphieeigenschaften und mittlere Kantendichte von Graphen
cites work: Degree and local connectivity in digraphs
cites work: Existence of vertices of local connectivity \(k\) in digraphs of large outdegree
cites work: Packing directed circuits
cites work: The Erdös-Sós conjecture for graphs without \(C_ 4\)
cites work: Characterization of even directed graphs
cites work: Some Homeomorphism Properties of Graphs
cites work: Sign-nonsingular matrices and even cycles in directed graphs
cites work: Q3491608
cites work: K5-Subdivisions in Graphs
description: scientific article