The \(m\)-degenerate chromatic number of a digraph

DOI10.1016/J.DISC.2016.01.024zbMATH Open1333.05110arXiv1409.7535OpenAlexW2282582397MaRDI QIDQ267198

Author name not available (Why is that?)

Publication date: 8 April 2016

Published in: (Search for Journal in Brave)

Abstract: The digraph chromatic number of a directed graph $D$, denoted $ch{i}_A(D)$, is the minimum positive integer $k$ such that there exists a partition of the vertices of $D$ into $k$ disjoint sets, each of which induces an acyclic subgraph. For any $mgeq1$, a digraph is weakly $m$-degenerate if each of its induced subgraphs has a vertex of in-degree or out-degree less than $m$. We introduce a generalization of the digraph chromatic number, namely $ch{i}_m(D)$, which is the minimum number of sets into which the vertices of a digraph $D$ can be partitioned so that each set induces a weakly $m$-degenerate subgraph. We show that for all digraphs $D$ without directed 2-cycles, $ch{i}_m(D)leqfrac2Delta(D)4m+1+O(1)$. Because $ch{i}_1(D)=ch{i}_A(D)$, we obtain as a corollary that $ch{i}_A(D)leq2/5cdotDelta(D)+O(1)$. We then use this bound to show that $ch{i}_A(D)leqsqrt2/3cdotildeDelta(D)+O(1)$, substantially improving a bound of Harutyunyan and Mohar that states that $ch{i}_A(D)leq(1-e^{-13})cdotildeDelta(D)$ for large enough $ildeDelta(D)$.

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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: The \(m\)-degenerate chromatic number of a digraph

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