- Tytuł:
- The Star Dichromatic Number
- Autorzy:
-
Hochstättler, Winfried
Steiner, Raphael - Powiązania:
- https://bibliotekanauki.pl/articles/32361737.pdf
- Data publikacji:
- 2022-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
dichromatic number
star chromatic number
circular dichromatic number - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 277-298
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł