Raphael Steiner - A Note on Graphs of Dichromatic Number 2

dmtcs:5621 - Discrete Mathematics & Theoretical Computer Science, January 5, 2021, vol. 22 no. 4 - https://doi.org/10.23638/DMTCS-22-4-11
A Note on Graphs of Dichromatic Number 2Article

Authors: Raphael Steiner ORCID1


Neumann-Lara and Škrekovski conjectured that every planar digraph is 2-colourable. We show that this conjecture is equivalent to the more general statement that all oriented K_5-minor-free graphs are 2-colourable.

https://doi.org/10.23638/DMTCS-22-4-11
Source: HAL:hal-02178422v3
Volume: vol. 22 no. 4
Section: Graph Theory
Published on: January 5, 2021
Accepted on: November 7, 2020
Submitted on: July 11, 2019
Keywords: [MATH]Mathematics [math], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] directed graphs, acyclic colouring, dichromatic number, planar graphs, K5-minor-free graphs

Share and export

Consultation statistics

This page has been seen 621 times.
This article's PDF has been downloaded 692 times.