Exploring the complexity boundary between coloring and list-coloring
2009, Annals of Operations Research 169 (1), 3-16, 2009Citas: 56
Agregar PDF Importar citas Plots Conexiones
Autor(es)
Flavia Bonomo and Guillermo Durán and Javier Marenco
Abstract
Many classes of graphs where the vertex coloring problem is polynomially solvable are known, the most prominent being the class of perfect graphs. However, the list-coloring problem is NP-complete for many subclasses of perfect graphs. In this work we explore the complexity boundary between vertex coloring and list-coloring on such subclasses of perfect graphs where the former admits polynomial-time algorithms but the latter is NP-complete. Our goal is to analyze the computational complexity of coloring problems lying “between” (from a computational complexity viewpoint) these two problems: precoloring extension, μ-coloring, and (γ,μ)-coloring.
Plot de citas
Citas de Scrapping
| # | Año | #Citas | Título | Autores | Journal | Editor |
|---|---|---|---|---|---|---|
| 1 | 2015 | 190 | An exact decomposition approach for the real-time train dispatching problem | L Lamorgese, C Mannino | Operations Research, 2015 | pubsonline.informs.org |
| 2 | 2017 | 147 | A survey on the computational complexity of coloring graphs with forbidden subgraphs | PA Golovach, M Johnson, D Paulusma… | Journal of Graph …, 2017 | Wiley Online Library |
| 3 | 2016 | 65 | Optimization methods for multistage freight train formation | M Bohlin, S Gestrelius, F Dahms… | Transportation …, 2016 | pubsonline.informs.org |
| 4 | 2022 | 15 | Pickup and delivery problems with autonomous vehicles on rings | M Trotta, C Archetti, D Feillet, A Quilliot | European Journal of Operational …, 2022 | Elsevier |
| 5 | 2014 | 45 | Closing complexity gaps for coloring problems on H-free graphs | PA Golovach, D Paulusma, J Song | Information and Computation, 2014 | Elsevier |
| 6 | 2015 | 32 | Open problems on graph coloring for special graph classes | D Paulusma | International Workshop on Graph-Theoretic Concepts …, 2015 | Springer |
| 7 | 2013 | 46 | Incremental list coloring of graphs, parameterized by conservation | S Hartung, R Niedermeier | Theoretical Computer Science, 2013 | Elsevier |
| 8 | 2011 | 40 | Track allocation in freight-train classification with mixed tracks | M Bohlin, H Flier, J Maue… | 11th workshop on …, 2011 | research-collection.ethz.ch |
| 9 | 2011 | 38 | Hump yard track allocation with temporary car storage | M Bohlin, H Flier, J Maue, M Mihalák | 4th International Seminar on …, 2011 | diva-portal.org |
| 10 | 2014 | 18 | Restricted coloring problems on Graphs with few P 4's | C Linhares-Sales, AK Maia, N Martins… | Annals of Operations …, 2014 | Springer |
| 11 | 2025 | 0 | An efficient backtracking heuristic for the resource allocation problem with compatibility and exclusivity constraints | A Khassiba | Journal of Heuristics, 2025 | Springer |
| 12 | 2019 | 42 | KK Dabrowski, M Johnson, D Paulusma | BCC, 2019 | ||
| 13 | 2013 | 23 | Constraint satisfaction problems: Convexity makes alldifferent constraints tractable | M Fellows, T Friedrich, D Hermelin… | Theoretical Computer …, 2013 | Elsevier |
| 14 | 2019 | 11 | Filling the complexity gaps for colouring planar and bounded degree graphs | KK Dabrowski, F Dross, M Johnson… | Journal of Graph …, 2019 | Wiley Online Library |
| 15 | 2302 | 0 | Adaptive large neighborhood search for a personnel task scheduling problem with task selection and parallel task assignments | M Gutjahr, SN Parragh, F Tricoire | arXiv preprint arXiv:2302.04494, 2023 | arxiv.org |
| 16 | 2019 | 5 | A branch and price algorithm for list coloring problem | M Lucci, G Nasini, D Severín | Electronic Notes in Theoretical Computer …, 2019 | Elsevier |
| 17 | 2012 | 9 | On coloring problems with local constraints | F Bonomo, Y Faenza, G Oriolo | Discrete Mathematics, 2012 | Elsevier |
| 18 | 2011 | 8 | Optimization of railway operations: algorithms, complexity, and models | HFR Flier | 2011 | research-collection.ethz.ch |
| 19 | 2016 | 8 | Polyhedral studies of vertex coloring problems: The standard formulation | D Delle Donne, J Marenco | Discrete Optimization, 2016 | Elsevier |
| 20 | 2019 | 4 | On the complexity of restoring corrupted colorings | M De Biasi, J Lauri | Journal of Combinatorial Optimization, 2019 | Springer |
| 21 | 2024 | 0 | On the Complexity of the Minimum Chromatic Violation Problem | D Delle Donne, M Escalante, ME Ugarte | International Symposium on …, 2024 | Springer |
| 22 | 2015 | 5 | Polyhedral studies of vertex coloring problems: The asymmetric representatives formulation | V Campos, RC Corrêa, DD Donne, J Marenco… | arXiv preprint arXiv …, 2015 | arxiv.org |
| 23 | 2015 | 6 | Mathematical models for optimising decision support systems in the railway industry | S Gestrelius | 2015 | diva-portal.org |
| 24 | 2014 | 6 | Limited packing and multiple domination problems: polynomial time reductions | V Leoni, G Nasini | Discrete Applied Mathematics, 2014 | Elsevier |
| 25 | 2021 | 2 | List Coloring of Block Graphs and Complete Bipartite Graphs | AK Sahakyan | World Science, 2021 | rsglobal.pl |
| 26 | 2012 | 6 | An exact decomposition approach for the real-time train dispatching problem | LC Lamorgese, C Mannino | SINTEF Rapport, 2012 | sintef.brage.unit.no |
| 27 | 2013 | 6 | Optimized shunting with mixed-usage tracks | M Bohlin, S Gestrelius, F Dahms, M Mihalák, H Flier | 2013 | diva-portal.org |
| 28 | 2012 | 7 | Closing Complexity Gaps for Coloring Problems on H-Free Graphs | PA Golovach, D Paulusma, J Song | Algorithms and Computation: 23rd …, 2012 | Springer |
| 29 | 2013 | 7 | On the Complexity of Global Scheduling Constraints under Structural Restrictions. | G Chu, S Gaspers, N Narodytska, A Schutt, T Walsh | IJCAI, 2013 | cse.unsw.edu |
| 30 | 2023 | 0 | Pickup and delivery problems with autonomous and electric vehicles | M Trotta | 2023 | theses.hal.science |
| 31 | 2023 | 1 | List Coloring Problem: A Heuristic Approach | S Srivastava, R Bansal… | Indian Journal …, 2023 | sciresol.s3.us-east-2.amazonaws … |
| 32 | 2023 | 0 | J Staszek | 2023 | Dissertation, Erlangen, Friedrich … | |
| 33 | 2016 | 6 | Estudios poliedrales de problemas de coloreo de grafos | DA Delle Donne | 2016 | bibliotecadigital.exactas.uba.ar |
| 34 | 2014 | 2 | Eternal chromatic number | M Anderson, R Brigham, RD Dutton… | Utilitas Mathematica, 2014 | researchgate.net |
| 35 | 2016 | 2 | Towards a Polynomial Equivalence Between-Packing Functions and k-Limited Packings in Graphs | V Leoni, MP Dobson | International Symposium on Combinatorial …, 2016 | Springer |
| 36 | 2023 | 0 | ON THE GRAPHS WITH DISTINGUISHING NUMBER EQUAL LIST DISTINGUISHING NUMBER. | S Alikhani, S Soltani | Journal of Mahani Mathematical …, 2023 | search.ebscohost.com |
| 37 | 2016 | 3 | Maximizing the total weight of just-in-time jobs under multi-slot conditions is NP-hard | E Chiba, S Imahori | IEICE TRANSACTIONS on Information and …, 2016 | search.ieice.org |
| 38 | 2015 | 2 | Scheduling and Sorting Algorithms for Robotic Warehousing Systems | D Graf | 2015 | research-collection.ethz.ch |
| 39 | 2010 | 6 | Contributions à l'analyse statique de programmes manipulant des tableaux | M Péron | 2010 | theses.hal.science |
| 40 | 0 | Check for updates On the Complexity of the Minimum Chromatic Violation Problem | D Delle Donne¹, M Escalante, ME Ugarte | … 8th International Symposium … | books.google.com | |
| 41 | 2023 | 0 | Resource allocation problem in a distributed real-time simulation platform | A Khassiba | ROADEF 2023, 24ème congrès annuel de la Société …, 2023 | hal.science |
| 42 | 2009 | 1 | On coloring problems with local constraints | F Bonomo, Y Faenza, G Oriolo | Electronic Notes in Discrete Mathematics, 2009 | Elsevier |
| 43 | 2016 | 2 | Sobre problemas de lista coloração ea propriedade de selecionabilidade em grafos | SIM Gama | 2016 | tede.ufam.edu.br |
| 44 | 2019 | 0 | Aspects of the complexity of (γ, µ)-coloring | S Gama, R de Freitas, US Souza | Matemática Contemporânea, 2019 | mc.sbm.org.br |
| 45 | 1812 | 0 | Choosability in bounded sequential list coloring | S Gama, R de Freitas, M Salvatierra | arXiv preprint arXiv:1812.11685, 2018 | arxiv.org |
| 46 | 2019 | 0 | COMPLETION of graphs with few P4 | AS de Abreu, FL Marquezino… | Matemática …, 2019 | mc.sbm.org.br |
| 47 | 2017 | 0 | Choosability in coloring problems of graphs with restricted color lists | S Gama, R de Freitas… | 2017 XLIII Latin American …, 2017 | ieeexplore.ieee.org |
| 48 | 2017 | 0 | Proactive Energy Management for Smart Building and Compute Server Architectures | A Majumdar | 2017 | search.proquest.com |
| 49 | 2016 | 0 | Matrix Partitions of Graphs: Algorithms and Complexity | M Mohammadi Nevisi | 2016 | summit.sfu.ca |
| 50 | 0 | 11vo Simposio Argentino de Investigacion Operativa, SIO 2013 | D Delle Donnea, J Marencob | academia.edu | ||
| 51 | 2013 | 0 | Graph Colouring with Input Restrictions | J Song | 2013 | etheses.dur.ac.uk |
| 52 | 0 | Estudios de complejidad del problema de mınima violación cromática en grafos | ME Ugarte | union-matematica.org.ar | ||
| 53 | 2011 | 1 | Teknisk slutrapport för RANPLAN-Beräkningstöd för planering och resursallokering på rangerbangården | S Gestrelius, M Bohlin, P Danielsson, M Aronsson | 2011 | diva-portal.org |
| 54 | 2019 | 0 | S Gama, R de Freitas, U Souza | Anais do IV Encontro de Teoria da …, 2019 | SBC | |
| 55 | 2019 | 0 | V Ponciano, R Oliveira | Anais do IV Encontro de Teoria da Computação, 2019 | SBC | |
| 56 | 0 | Algoritmos e complexidade computacional de problemas de listas coloraç oes limitadas ea propriedade da selecionabilidade em grafos | S Gama, R de Freitas, M Salvatierra | din.uem.br | ||
| 57 | 2015 | 0 | Sobre o Problema da Lista Coloração em Grafos | NM Dantas | 2015 | riu.ufam.edu.br |
| 58 | 2013 | 0 | Polyhedral studies on vertex coloring problems | D Delle Donne, J Marenco | XI Simposio Argentino de …, 2013 | sedici.unlp.edu.ar |
| 59 | 2012 | 0 | Masterarbeit im Fach Mathematik | T Güçlü | 2012 | or.rwth-aachen.de |
| 60 | 0 | AS de Abreu, FL Marquezino, DFD Posner | Matemática Contemporânea |