DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

W. Hochstättler, R. Steiner

Title:

The star dichromatic number

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-01-29, Revised: 2019-10-03, Accepted: 2019-10-03, 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 \cite{vince} 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

PDF
Close