The star dichromatic number

DOI10.7151/DMGT.2261MaRDI QIDQ2062686zbMATH OpenOpenAlexFDO

Authors Winfried. Hochstättler, Raphael Steiner

Publication date 3 January 2022

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://arxiv.org/abs/1809.00142

zbMATH Keywords

circular dichromatic number.dichromatic numberstar chromatic number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Abstract: We introduce a new notion of circular colourings for digraphs. The idea of this quantity, called star dichromatic number $vec{chi}^{a}st(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 by Wang et al. and resembles the concept of the star chromatic number of graphs introduced by 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 by Bokal et al. and point out similarities as well as differences in certain situations. As it turns out, the star dichromatic number is a lower bound for the circular dichromatic number of Bokal et al., but the gap between the numbers may be arbitrarily close to $1$. We conclude with a discussion of the case of planar digraphs and point out some open problems.

Review text

Motivated by the notion of star chromatic number [\textit{A. Vince}, J. Graph Theory 12, No. 4, 551--559 (1988; Zbl 0658.05028)] and the notion of circular chromatic number of a digraph [\textit{D. Bokal} et al., ibid. 46, No. 3, 227--240 (2004; Zbl 1041.05026)], the authors extend these invariant to the so-called star dichromatic number. In their paper, some basic properties of the star dichromatic number are presented, its relation to other fractional chromatic invariants of digraphs are investigated, and the values of the invariant for planar graphs are discussed.

Recommendations

• On the complexity of digraph colourings and vertex arboricity
• The circular chromatic numbers of planar digraphs
• The circular chromatic number of a digraph
• scientific article; zbMATH DE number 3918396
• Circular coloring of planar digraphs

Cites work

• A Minimax Theorem for Directed Graphs
• Acyclic Homomorphisms and Circular Colorings of Digraphs
• Circular chromatic number: A survey
• Circular colorings of edge-weighted graphs
• Circular vertex arboricity
• Combinatorial optimization. Packing and covering
• Dichromatic number and fractional chromatic number
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• On the complexity of digraph colourings and vertex arboricity
• On the width—length inequality
• Planar digraphs of digirth four are 2-colorable
• Planar digraphs without large acyclic sets
• Star chromatic number
• The circular chromatic number of a digraph
• The Point-Arboricity of Planar Graphs
• Two results on the digraph chromatic number

Cited in

(3)

• Colouring non-even digraphs
• scientific article; zbMATH DE number 5572871 (Why is no real title available?)
• Star Chromatic Index

This page was built for publication: The star dichromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2062686)