Complexity of list coloring problems with a fixed total number of colors

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)

zbMATH Keywords

complexitylist coloringtreed graphs

Mathematics Subject Classification ID

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