Planar Digraphs of Digirth Four are 2-Colorable
From MaRDI portal
Publication:5361236
DOI10.1137/16M108080XzbMath1371.05089arXiv1606.06114OpenAlexW2963663369MaRDI QIDQ5361236
Publication date: 27 September 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1606.06114
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)
Related Items
On the dichromatic number of surfaces ⋮ Acyclic coloring parameterized by directed clique-width ⋮ Cuts in matchings of 3-connected cubic graphs ⋮ The digrundy number of digraphs ⋮ The minimum number of edges in 4-critical digraphs of given order ⋮ Complete acyclic colorings ⋮ Decomposing and colouring some locally semicomplete digraphs ⋮ Four proofs of the directed Brooks' theorem ⋮ Cycle reversions and dichromatic number in tournaments ⋮ Reducing the dichromatic number via cycle reversions in infinite digraphs ⋮ Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ Small feedback vertex sets in planar digraphs ⋮ A note on coloring digraphs of large girth ⋮ The diachromatic number of digraphs ⋮ Extension of Gyárfás-Sumner conjecture to digraphs ⋮ The chromatic polynomial of a digraph ⋮ Hajós and Ore constructions for digraphs ⋮ The star dichromatic number ⋮ Dichromatic number and forced subdivisions ⋮ Colouring non-even digraphs ⋮ Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth
Cites Work
- Small feedback vertex sets in planar digraphs
- Bridges and Hamiltonian circuits in planar graphs
- The dichromatic number of a digraph
- Acyclic subgraphs of planar digraphs
- Planar Digraphs of Digirth Five Are 2-Colorable
- A Theorem on Planar Graphs
- The circular chromatic number of a digraph
- A theorem on paths in planar graphs
