The star dichromatic number
METADATA ONLY
Author / Producer
Date
2022
Publication Type
Journal Article
ETH Bibliography
no
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
42 (1)
Pages / Article No.
277 - 298
Publisher
University of Zielona Góra Press
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
dichromatic number; star chromatic number; circular dichromatic number
Organisational unit
03672 - Steger, Angelika (emeritus) / Steger, Angelika (emeritus)