Geodesic
The Star Dichromatic Number
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 277-298.

Voir la notice de l'article provenant de la source Library of Science

We introduce a new notion of circular colourings for digraphs. The idea of this quantity, called star dichromatic number χ⃗^∗ (D) of a digraph D, is to allow a finer subdivision of digraphs with the same dichromatic number into such which are “easier” or “harder” to colour by allowing fractional values. This is related to a coherent notion for the vertex arboricity of graphs introduced in [G. Wang, S. Zhou, G. Liu and J. Wu, Circular vertex arboricity, J. Discrete Appl. Math. 159 (2011) 1231–1238] and resembles the concept of the star chromatic number of graphs introduced by Vince in [15] in the framework of digraph colouring. After presenting basic properties of the new quantity, including range, simple classes of digraphs, general inequalities and its relation to integer counterparts as well as other concepts of fractional colouring, we compare our notion with the notion of circular colourings for digraphs introduced in [D. Bokal, G. Fijavz, M. Juvan, P.M. Kayll and B. Mohar, The circular chromatic number of a digraph, J. Graph Theory 46 (2004) 227–224] and point out similarities as well as differences in certain situations. As it turns out, the star dichromatic number shares all positive characteristics with the circular dichromatic number of Bokal et al., but has the advantage that it depends on the strong components of the digraph only, while the addition of a dominating source raises the circular dichromatic number to the ceiling. We conclude with a discussion of the case of planar digraphs and point out some open problems.
Keywords: dichromatic number, star chromatic number, circular dichromatic number 
@article{DMGT_2022_42_1_a17,
     author = {Hochst\"attler, Winfried and Steiner, Raphael},
     title = {The {Star} {Dichromatic} {Number}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {277--298},
     publisher = {mathdoc},
     volume = {42},
     number = {1},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a17/}
}
TY  - JOUR
AU  - Hochstättler, Winfried
AU  - Steiner, Raphael
TI  - The Star Dichromatic Number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 277
EP  - 298
VL  - 42
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a17/
LA  - en
ID  - DMGT_2022_42_1_a17
ER  - 
%0 Journal Article
%A Hochstättler, Winfried
%A Steiner, Raphael
%T The Star Dichromatic Number
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 277-298
%V 42
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a17/
%G en
%F DMGT_2022_42_1_a17
Hochstättler, Winfried; Steiner, Raphael. The Star Dichromatic Number. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 277-298. http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a17/

[1] D. Bokal, G. Fijavz, M. Juvan, P.M. Kayll and B. Mohar, The circular chromatic number of a digraph, J. Graph Theory 46 (2004) 227–224. https://doi.org/10.1002/jgt.20003

[2] G. Chartrand and H.V. Kronk, The point-arboricity of planar graphs, J. London Math. Soc. 44 (1969) 612–616. https://doi.org/10.1112/jlms/s1-44.1.612

[3] G. Cornuéjols, Combinatorial Optimization: Packing and Covering (SIAM, Philadelphia, 2001). https://doi.org/10.1137/1.9780898717105

[4] T. Feder, P. Hell and B. Mohar, Acyclic homomorphisms and circular colorings of digraphs, SIAM J. Discrete Math. 17 (2003) 161–169. https://doi.org/10.1137/S0895480103422184

[5] A. Harutyunyan and B. Mohar, Two results on the digraph chromatic number, J. Discrete Math. 312 (2012) 1823–1826. https://doi.org/10.1016/j.disc.2012.01.028

[6] W. Hochstättler, F. Schröder and R. Steiner, On the complexity of digraph colourings and vertex arboricity, Discrete Math. Theor. Comput. Sci. 22 (2020) #4. https://doi.org/10.23638/DMTCS-22-1-4

[7] K. Knauer, P. Valicov and P.S. Wenger, Planar digraphs without large acyclic sets, J. Graph Theory 85 (2017) 288–291. https://doi.org/10.1002/jgt.22061

[8] Z. Li and B. Mohar, Planar digraphs of digirth four are 2 -colorable, SIAM J. Discrete Math. 31 (2017) 2201–2205. https://doi.org/10.1137/16M108080X

[9] A. Lehman, On the width-length inequality, Math. Program. 17 (1979) 403–417. https://doi.org/10.1007/BF01588263

[10] C.L. Lucchesi and D.H. Younger, A minimax theorem for directed graphs, J. London Math. Soc. (2) 17 (1978) 369–374. https://doi.org/10.1112/jlms/s2-17.3.369

[11] B. Mohar, Circular colorings of edge-weighted graphs, J. Graph Theory 43 (2003) 107–116. https://doi.org/10.1002/jgt.10106

[12] B. Mohar and H. Wu, Dichromatic number and fractional chromatic number, Forum Math. Sigma 4 (2016) e32. https://doi.org/10.1017/fms.2016.28

[13] E.R. Scheinerman and D.H. Ullman, Fractional Graph Theory: A Rational Approach to the Theory of Graphs (Dover Publications, Mineola, New York, 2013).

[14] R. Steiner, Neumann-Lara-Flows and the Two-Colour-Conjecture (Master’s Thesis, FernUniversität in Hagen, 2018).

[15] A. Vince, Star chromatic number, J. Graph Theory 12 (1988) 551–559. https://doi.org/10.1002/jgt.3190120411

[16] G. Wang, S. Zhou, G. Liu and J. Wu, Circular vertex arboricity, J. Discrete Appl. Math. 159 (2011) 1231–1238. https://doi.org/10.1016/j.dam.2011.04.009

[17] Woodall’s Conjecture, at Open Problem Garden. http://www.openproblemgarden.org/op/woodallsσconjecture

[18] X. Zhu, Circular chromatic number: A survey, J. Discrete Math. 229 (2001) 371–410. https://doi.org/10.1016/S0012-365X(00)00217-X