Article in volume
Authors:
Title:
The star dichromatic number
PDFSource:
Discussiones Mathematicae Graph Theory 42(1) (2022) 277-298
Received: 2019-01-29 , Revised: 2019-10-03 , Accepted: 2019-10-03 , Available online: 2019-11-21 , https://doi.org/10.7151/dmgt.2261
Abstract:
We introduce a new notion of circular colourings for digraphs. The idea of this
quantity, called star dichromatic number $\vec{\chi}^\ast(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
References:
- 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 - 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 - G. Cornuéjols, Combinatorial Optimization: Packing and Covering (SIAM, Philadelphia, 2001).
https://doi.org/10.1137/1.9780898717105 - 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 - 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 - 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 - 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 - 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 - A. Lehman, On the width-length inequality, Math. Program. 17 (1979) 403–417.
https://doi.org/10.1007/BF01588263 - 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 - B. Mohar, Circular colorings of edge-weighted graphs, J. Graph Theory 43 (2003) 107–116.
https://doi.org/10.1002/jgt.10106 - 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 - E.R. Scheinerman and D.H. Ullman, Fractional Graph Theory: A Rational Approach to the Theory of Graphs (Dover Publications, Mineola, New York, 2013).
- R. Steiner, Neumann-Lara-Flows and the Two-Colour-Conjecture (Master's Thesis, FernUniversität in Hagen, 2018).
- A. Vince, Star chromatic number, J. Graph Theory 12 (1988) 551–559.
https://doi.org/10.1002/jgt.3190120411 - 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 - Woodall's Conjecture, at Open Problem Garden.
http://www.openproblemgarden.org/op/woodalls_conjecture - X. Zhu, Circular chromatic number: A survey, J. Discrete Math. 229 (2001) 371–410.
https://doi.org/10.1016/S0012-365X(00)00217-X
Close