Two results on the digraph chromatic number

DOI10.1016/J.DISC.2012.01.028zbMATH Open1242.05095arXiv1110.4898OpenAlexW2046546000MaRDI QIDQ418896

Author name not available (Why is that?)

Publication date: 30 May 2012

Published in: (Search for Journal in Brave)

Abstract: It is known (Bollob'{a}s (1978); Kostochka and Mazurova (1977)) that there exist graphs of maximum degree $Delta$ and of arbitrarily large girth whose chromatic number is at least $cDelta/logDelta$. We show an analogous result for digraphs where the chromatic number of a digraph $D$ is defined as the minimum integer $k$ so that $V(D)$ can be partitioned into $k$ acyclic sets, and the girth is the length of the shortest cycle in the corresponding undirected graph. It is also shown, in the same vein as an old result of Erdos (1962), that there are digraphs with arbitrarily large chromatic number where every large subset of vertices is 2-colorable.

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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Two results on the digraph chromatic number

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