Gallai's Theorem for List Coloring of Digraphs

DOI10.1137/100803870zbMath1330.05068OpenAlexW2046684958MaRDI QIDQ3094906

Bojan Mohar, Ararat Harutyunyan

Publication date: 27 October 2011

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

Full work available at URL: https://semanticscholar.org/paper/0d2f018fd4466f54e905ace75e9ca1a642e7671e

zbMATH Keywords

algorithmic complexityNP-completelist coloringdigraph coloringdichromatic numbercritical digraphGallai tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (10)

On the dichromatic number of surfaces ⋮ Digraphs and Variable Degeneracy ⋮ Four proofs of the directed Brooks' theorem ⋮ Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph ⋮ Two results on the digraph chromatic number ⋮ Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring ⋮ Coloring digraphs with forbidden cycles ⋮ The edge density of critical digraphs ⋮ Hajós and Ore constructions for digraphs ⋮ Coloring tournaments: from local to global

This page was built for publication: Gallai's Theorem for List Coloring of Digraphs