A Note on Graphs of Dichromatic Number 2

被引：0

作者：

Steiner, Raphael ^{[1
]}

机构：

[1] Tech Univ Berlin, Inst Math, Str 17 Juni 136, Berlin, Germany

来源：

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | 2020年 / 22卷 / 04期

关键词：

directed graphs; acyclic colouring; dichromatic number; planar graphs; K-5-minor-free graphs;

D O I：

10.23638/DMTCS-22-4-11

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Neumann-Lara and Skrekovski 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.

引用

页数：7

共 12 条

[1]

Aboulker P, 2019, ELECTRON J COMB, V26

[2] Perfect Digraphs [J].

Andres, Stephan Dominique ;

Hochstaettler, Winfried .

JOURNAL OF GRAPH THEORY, 2015, 79 (01) :21-29

[3] List coloring digraphs [J].

Bensmail, Julien ;

Harutyunyan, Ararat ;

Ngoc Khang Le .

JOURNAL OF GRAPH THEORY, 2018, 87 (04) :492-508

[4] The circular chromatic number of a digraph [J].

Bokal, D ;

Fijavz, G ;

Juvan, M ;

Kayll, PM ;

Mohar, B .

JOURNAL OF GRAPH THEORY, 2004, 46 (03) :227-240

[5] Coloring tournaments: From local to global [J].

Harutyunyan, Ararat ;

Tien-Nam Le ;

Thomasse, Stephan ;

Wu, Hehui .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 138 :166-171

[6] Planar Digraphs of Digirth Five Are 2-Colorable [J].

Harutyunyan, Ararat ;

Mohar, Bojan .

JOURNAL OF GRAPH THEORY, 2017, 84 (04) :408-427

[7] PLANAR DIGRAPHS OF DIGIRTH FOUR ARE 2-COLORABLE [J].

Li, Zhentao ;

Mohar, Bojan .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (03) :2201-2205

[8] Circular colorings of edge-weighted graphs [J].

Mohar, B .

JOURNAL OF GRAPH THEORY, 2003, 43 (02) :107-116

[9] DICHROMATIC NUMBER AND FRACTIONAL CHROMATIC NUMBER [J].

Mohar, Bojan ;

Wu, Hehui .

FORUM OF MATHEMATICS SIGMA, 2016, 4

[10]

Neumann-Lara V., 1985, TECHNICAL REPORT

← 1 2 →