Digraphs and variable degeneracy

DOI10.1137/20M1386827MaRDI QIDQ5062115zbMATH OpenOpenAlexFDO

Authors Thomas Schweser, Jørgen Bang-Jensen, Michael Stiebitz

Publication date 15 March 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

acyclic digraphBrooks' theoremdigraph coloringdigraph degeneracy

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Abstract: Let $D$ be a digraph, let $pgeq1$ be an integer, and let $f:V(D)omathbb{N}_0^p$ be a vector function with $f=(f_1,f_2,ldots,f_p)$. We say that $D$ has an $f$-partition if there is a partition $(D_1,D_2,ldots,D_p)$ into induced subdigraphs of $D$ such that for all $iin[1,p]$, the digraph $D_i$ is weakly $f_i$-degenerate, that is, in every non-empty subdigraph $D^{\prime }$ of $D_i$ there is a vertex $v$ such that $min{d}_{D^{\prime }}^{+}(v),d_{D^{\prime }}^{-}(v)<f_i(v)$. In this paper, we prove that the condition $f_1(v)+f_2(v)+ldots+f_p(v)geqmax{d}_D^{+}(v),d_D^{-}(v)$ for all $vinV(D)$ is almost sufficient for the existence of an $f$-partition and give a full characterization of the bad pairs $(D,f)$. Moreover, we describe a polynomial time algorithm that (under the previous conditions) either verifies that $(D,f)$ is a bad pair or finds an $f$-partition. Among other applications, this leads to a generalization of Brooks' Theorem as well as the list-version of Brooks' Theorem for digraphs, where a coloring of digraph is a partition of the digraph into acyclic induced subdigraphs. We furthermore obtain a result bounding the $s$-degenerate chromatic number of a digraph in terms of the maximum of maximum in-degree and maximum out-degree.

Recommendations

• The \(m\)-degenerate chromatic number of a digraph
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems
• Out-degree reducing partitions of digraphs
• Partitioning the vertices of a digraph into directed cycles and degenerated directed cycles
• Partitioning a graph into degenerate subgraphs

Cites work

• A conjecture of Neumann-Lara on infinite families of \(r\)-dichromatic circulant tournaments
• Acyclic systems of representatives and acyclic colorings of digraphs
• An extension of Brooks' theorem to n-degenerate graphs
• Brooks' Theorem and Beyond
• Chromatic number, girth and maximal degree
• Circular colorings of edge-weighted graphs
• Critical Point-Arboritic Graphs
• Eigenvalues and colorings of digraphs
• Gallai's theorem for list coloring of digraphs
• Graph theory
• Hajós and Ore constructions for digraphs
• Hajós theorem for colorings of edge-weighted graphs
• scientific article; zbMATH DE number 3659621 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Perfect digraphs
• Strengthened Brooks' theorem for digraphs of girth at least three
• The \(m\)-degenerate chromatic number of a digraph
• The circular chromatic number of a digraph
• The dichromatic number of a digraph
• The edge density of critical digraphs
• The Point Partition Numbers of Closed 2-Manifolds
• The strong perfect graph theorem
• Two results on the digraph chromatic number
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems

Cited in

(4)

• Cover and variable degeneracy
• Partitioning into degenerate graphs in linear time
• Four proofs of the directed Brooks' theorem
• Brooks-type colourings of digraphs in linear time

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Digraphs and variable degeneracy

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