Subdivisions of oriented cycles in digraphs with large chromatic number

DOI10.1002/JGT.22360zbMATH Open1484.05083arXiv1605.07762OpenAlexW2963205193MaRDI QIDQ4646948FDOQ4646948

Authors: Nathann Cohen, Frédéric Havet, William Lochet, Nicolas Nisse 

Publication date: 3 January 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle $C$, there are digraphs containing no subdivision of $C$ (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that for any $C$ a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of $C$. We prove a similar result for the antidirected cycle on four vertices (in which two vertices have out-degree $2$ and two vertices have in-degree $2$).

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

Recommendations

• Subdivisions of four blocks cycles in digraphs with large chromatic number
• Subdivisions of oriented cycles in Hamiltonian digraphs with small chromatic number
• Dichromatic number and forced subdivisions
• Two results on the digraph chromatic number
• Cycles with two blocks in \(k\)-chromatic digraphs

zbMATH Keywords

digraphcoloringsubdivision

Mathematics Subject Classification ID

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

Cited In (16)

• Two results on the digraph 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
• Existence of paths with \(t\) blocks in \(k ( t )\)-chromatic digraph
• Antidirected subgraphs of oriented graphs
• Subdivisions in digraphs of large out-degree or large dichromatic number
• Tournaments and Semicomplete Digraphs
• On bispindles \(B(k_1,k_2;1)\) in strongly connected digraphs with large chromatic number
• Subdivisions of four blocks cycles in digraphs with large chromatic number
• Dichromatic number and forced subdivisions
• Secant edges: a tool for Cohen et al.'s conjectures about subdivisions of oriented cycles and bispindles in Hamiltonian digraphs with large chromatic number
• On three blocks paths \(P (k, l, r)\)
• Bispindle in strongly connected digraphs with large chromatic number
• Subdivisions of oriented cycles in Hamiltonian digraphs with small chromatic number
• Oriented flip graphs of polygonal subdivisions and noncrossing tree partitions

This page was built for publication: Subdivisions of oriented cycles in digraphs with large chromatic number

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