Complexity of list coloring problems with a fixed total number of colors
From MaRDI portal
Publication:1348378
DOI10.1016/S0166-218X(01)00179-2zbMath0990.05042MaRDI QIDQ1348378
Sylvain Gravier, Daniel Kobler, Wiesław X. Kubiak
Publication date: 15 May 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees ⋮ Bounded max-colorings of graphs ⋮ Covering Graphs with Few Complete Bipartite Subgraphs ⋮ Locally boundedk-colorings of trees ⋮ Covering graphs with few complete bipartite subgraphs ⋮ Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Proportional choosability: a new list analogue of equitable coloring
Cites Work
- On the X-join decomposition for undirected graphs
- Complement reducible graphs
- Precoloring extension. I: Interval graphs
- On the complexity of a restricted list-coloring problem
- Restricted coloring models for timetabling
- Generalized coloring for tree-like graphs
- Arrays of distinct representatives --- a very simple NP-complete problem
- On the vertex packing problem
- Normal hypergraphs and the perfect graph conjecture
- On a property of the class of n-colorable graphs
- A Fast Algorithm for the Decomposition of Graphs and Posets
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item