Exploring the complexity boundary between coloring and list-coloring
DOI10.1016/J.ENDM.2006.06.064zbMATH Open1134.68374OpenAlexW2008738950MaRDI QIDQ5899384FDOQ5899384
Authors: Flavia Bonomo, Guillermo Durán, Javier Marenco 
Publication date: 29 May 2007
Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.endm.2006.06.064
Recommendations
- Exploring the complexity boundary between coloring and list-coloring
- Algorithmic complexity of list colorings
- Publication:4934399
- On the complexity of a restricted list-coloring problem
- Complexity of list coloring problems with a fixed total number of colors
- List Set Colouring: Bounds and Algorithms
- scientific article; zbMATH DE number 1560505
- Parameterized complexity of list coloring and max coloring
- Space complexity of list H-colouring: a dichotomy
- Near-optimal list colorings
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)
Cites Work
- The ellipsoid method and its consequences in combinatorial optimization
- The NP-Completeness of Edge-Coloring
- The complexity of completing partial Latin squares
- Graph colorings with local constraints -- a survey
- Generalized coloring for tree-like graphs
- Precoloring extension. I: Interval graphs
- Title not available (Why is that?)
- Precoloring Extension III: Classes of Perfect Graphs
- Some results concerning the complexity of restricted colorings of graphs
- Title not available (Why is that?)
Cited In (7)
- Space complexity of list H-colouring: a dichotomy
- Exploring the complexity boundary between coloring and list-coloring
- Between coloring and list-coloring: \(\mu \)-coloring.
- Aspects of the complexity of \((\gamma,\mu)\)-coloring
- Algorithmic complexity of list colorings
- Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem
- Solving a real-world train-unit assignment problem
This page was built for publication: Exploring the complexity boundary between coloring and list-coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5899384)
