We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
THE STAR DICHROMATIC NUMBER.
- Authors
HOCHSTÄTTLER, WINFRIED; STEINER, RAPHAEL
- Abstract
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.
- Subjects
GRAPH theory; SIMILARITY (Geometry); CHROMATIC polynomial; COLOR
- Publication
Discussiones Mathematicae: Graph Theory, 2022, Vol 42, Issue 1, p277
- ISSN
1234-3099
- Publication type
Article
- DOI
10.7151/dmgt.2261