Gallai's Theorem for List Coloring of Digraphs
Authors:
- Ararat HarutyunyanAHArarat Harutyunyan
- Bojan MoharBMBojan Mohar
- 1 January 2011
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 25 (1) , 170-180
Abstract
A classical theorem of Gallai states that in every graph that is critical for k-colorings, the vertices of degree $k-1$ induce a tree-like graph whose blocks are either complete graphs or cycles of odd length. We provide a generalization to colorings and list colorings of digraphs, where some new phenomena arise. In particular, the problem of list coloring digraphs with the lists at each vertex v having $\min\{d^{+}(v),d^{-}(v)\}$ colors turns out to be NP-hard.
Keywords
This publication has 9 references indexed in Scilit:
- Eigenvalues and colorings of digraphsLinear Algebra and its Applications, 2010
- The circular chromatic number of a digraphJournal of Graph Theory, 2004
- Circular colorings of edge‐weighted graphsJournal of Graph Theory, 2003
- Acyclic Homomorphisms and Circular Colorings of DigraphsSIAM Journal on Discrete Mathematics, 2003
- Digraphs2002
- Color-Critical Graphs on a Fixed SurfaceJournal of Combinatorial Theory, Series B, 1997
- The colour theorems of Brooks and Gallai extendedDiscrete Mathematics, 1996
- The complexity of induced minors and related problemsAlgorithmica, 1995
- The dichromatic number of a digraphJournal of Combinatorial Theory, Series B, 1982