Planar digraphs of digirth five are 2-colorable

DOI10.1002/JGT.22032MaRDI QIDQ2978182zbMATH OpenOpenAlexFDO

Authors Ararat Harutyunyan, Bojan Mohar

Publication date 21 April 2017

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

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

zbMATH Keywords

dichromatic numberdigraph chromatic numberdischargingplanar digraph

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)

Abstract: Neumann-Lara (1985) and v{S}krekovski conjectured that every planar digraph with digirth at least three is 2-colorable. We prove a relaxed version of this conjecture: every planar digraph of digirth at least five is 2-colorable. The result also holds in the setting of list colorings.

Recommendations

• Planar digraphs of digirth four are 2-colorable
• A note on coloring digraphs of large girth
• Circular coloring of planar digraphs
• Colouring non-even digraphs
• Coloring digraphs with forbidden cycles

Cites work

• The circular chromatic number of a digraph
• The dichromatic number of a digraph
• The point-arboricity of a graph

Cited in

(8)

• A note on coloring digraphs of large girth
• Dichromatic number and forced subdivisions
• Colouring non-even digraphs
• Acyclic subgraphs of planar digraphs
• Acyclic digraphs
• Planar digraphs without large acyclic sets
• Small feedback vertex sets in planar digraphs
• Planar digraphs of digirth four are 2-colorable

This page was built for publication: Planar digraphs of digirth five are 2-colorable

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