Dichromatic number and forced subdivisions

DOI10.1016/J.JCTB.2021.10.002MaRDI QIDQ2072176zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 26 January 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

dichromatic numberdigraphsubdivisiontopological minor

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Graph minors (05C83)

Abstract: We investigate bounds on the dichromatic number of digraphs which avoid a fixed digraph as a topological minor. For a digraph $F$, denote by $ext{mader}_{vecchi}(F)$ the smallest integer $k$ such that every $k$-dichromatic digraph contains a subdivision of $F$. As our first main result, we prove that if $F$ is an orientation of a cycle then $ext{mader}_{vecchi}(F)=v(F)$. This settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura and Thomass'{e}. We also extend this result to the more general class of orientations of cactus graphs, and to bioriented forests. Our second main result is that $ext{mader}_{vecchi}(F)=4$ for every tournament $F$ of order $4$. This is an extension of the classical result by Dirac that $4$-chromatic graphs contain a $K_4$-subdivision to directed graphs.

Recommendations

• Dichromatic number and fractional chromatic number
• Split and non-split dominator chromatic numbers
• Subdivisions and chromatic roots
• Dichromatic sums revisited
• Subdivisions in digraphs of large out-degree or large dichromatic number
• Subcolorings and the subchromatic number of a graph
• Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
• A flow theory for the dichromatic number
• Chromatic number, induced cycles, and non-separating cycles
• Chromatic number and subtrees of graphs

Cites work

• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
• Circular colorings of edge-weighted graphs
• Coloring tournaments: from local to global
• Dichromatic number and fractional chromatic number
• Even cycles in directed graphs
• Finding a subdivision of a prescribed digraph of order 4
• Hajos' graph-coloring conjecture: Variations and counterexamples
• scientific article; zbMATH DE number 3687449 (Why is no real title available?)
• scientific article; zbMATH DE number 3708430 (Why is no real title available?)
• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• List coloring digraphs
• On the conjecture of Hajos
• On topological tournaments of order 4 in digraphs of outdegree 3
• Perfect digraphs
• Planar digraphs of digirth five are 2-colorable
• Planar digraphs of digirth four are 2-colorable
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Short proof of Menger's theorem
• Some remarks on Hajós' conjecture
• Subdivisions in digraphs of large out-degree or large dichromatic number
• Subdivisions of digraphs in tournaments
• Subdivisions of oriented cycles in digraphs with large chromatic number
• The dichromatic number of a digraph
• Topological cliques in graphs II
• Vertices of small degree in critically n-connected digraphs

Cited in

(18)

• Subdivisions of oriented cycles in Hamiltonian digraphs with small chromatic number
• Subdivisions of four blocks cycles in digraphs with large chromatic number
• Subdivisions in digraphs of large out-degree or large dichromatic number
• Decomposing and colouring some locally semicomplete digraphs
• Dichromatic number and fractional chromatic number
• scientific article; zbMATH DE number 3918396 (Why is no real title available?)
• Finding a subdivision of a prescribed digraph of order 4
• Subdivisions of oriented cycles in digraphs with large chromatic number
• Strong complete minors in digraphs
• Complete directed minors and chromatic number
• Four proofs of the directed Brooks' theorem
• Some mader-perfect graph classes
• Subdivisions with congruence constraints in digraphs of large chromatic number
• Subdivisions in dicritical digraphs with large order or digirth
• Antidirected subgraphs of oriented graphs
• The dichromatic number of digraphs without induced subdigraphs
• Tight minimum degree conditions for apex-outerplanar minors and subdivisions in graphs and digraphs
• Clique number of tournaments

This page was built for publication: Dichromatic number and forced subdivisions

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