Subdivisions in digraphs of large out-degree or large dichromatic number

zbMATH Open1417.05083arXiv1610.00876MaRDI QIDQ2315440FDOQ2315440

Authors: Pierre Aboulker, Nathann Cohen, William Lochet, Phablo F. S. Moura, Frédéric Havet, Stéphan Thomassé 

Publication date: 5 August 2019

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1610.00876

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• A note on complete subdivisions in digraphs of large outdegree
• Dichromatic number and forced subdivisions
• Subdivisions of digraphs in tournaments
• Subdivisions of oriented cycles in digraphs with large chromatic number

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15)

Cites Work

• The Erdös-Sós conjecture for graphs without \(C_ 4\)
• The Erdös-Sós conjecture for graphs of girth 5
• Tree embeddings
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Sign-nonsingular matrices and even cycles in directed graphs
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Topological cliques in graphs II
• Title not available (Why is that?)
• Title not available (Why is that?)
• Oriented trees in digraphs
• Title not available (Why is that?)
• Packing directed circuits
• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
• Cycles in digraphs– a survey
• Degree and local connectivity in digraphs
• Existence of vertices of local connectivity \(k\) in digraphs of large outdegree
• Immersing complete digraphs
• K₅-Subdivisions in Graphs
• Characterization of even directed graphs
• Disjoint directed cycles
• Some Homeomorphism Properties of Graphs
• Subdivisions of oriented cycles in digraphs with large chromatic number
• Short proof of Menger's theorem
• Antidirected Subtrees of Directed Graphs
• The directed grid theorem

Cited In (17)

• A note on coloring digraphs of large girth
• Some mader-perfect graph classes
• Extension of Gyárfás-Sumner conjecture to digraphs
• Complete directed minors and chromatic number
• Bispindles in strongly connected digraphs with large chromatic number
• Subdivisions in dicritical digraphs with large order or digirth
• Subdivisions with congruence constraints in digraphs of large chromatic number
• Digraph coloring and distance to acyclicity
• Strong complete minors in digraphs
• Antidirected subgraphs of oriented graphs
• Decomposing and colouring some locally semicomplete digraphs
• Four proofs of the directed Brooks' theorem
• Spanning subdivisions in dense digraphs
• Dichromatic number and forced subdivisions
• Out-degree reducing partitions of digraphs
• A note on complete subdivisions in digraphs of large outdegree
• Acyclic coloring of products of digraphs

This page was built for publication: Subdivisions in digraphs of large out-degree or large dichromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2315440)