Digraphs and Variable Degeneracy

DOI10.1137/20M1386827zbMath1484.05081arXiv2012.09713OpenAlexW4214845824MaRDI QIDQ5062115

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

Brooks' theoremdigraph coloringacyclic digraphdigraph degeneracy

Mathematics Subject Classification ID

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

Related Items (2)

Partitioning into degenerate graphs in linear time ⋮ Four proofs of the directed Brooks' theorem

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The \(m\)-degenerate chromatic number of a digraph
• Two results on the digraph chromatic number
• The edge density of critical digraphs
• Strengthened Brooks' theorem for digraphs of girth at least three
• The strong perfect graph theorem
• A conjecture of Neumann-Lara on infinite families of \(r\)-dichromatic circulant tournaments
• Eigenvalues and colorings of digraphs
• An extension of Brooks' theorem to n-degenerate graphs
• Chromatic number, girth and maximal degree
• The dichromatic number of a digraph
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems
• Hajós and Ore constructions for digraphs
• Hajós theorem for colorings of edge-weighted graphs
• Graph Theory
• Gallai's Theorem for List Coloring of Digraphs
• Brooks' Theorem and Beyond
• Acyclic systems of representatives and acyclic colorings of digraphs
• Critical Point-Arboritic Graphs
• Circular colorings of edge-weighted graphs
• The circular chromatic number of a digraph
• Perfect Digraphs
• The Point Partition Numbers of Closed 2-Manifolds

This page was built for publication: Digraphs and Variable Degeneracy