Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2512.16807 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918256324902912 |
|---|---|
| author | Gama, Simone Ingrid Monteiro Rodrigues, Rosiane de Freitas |
| author_facet | Gama, Simone Ingrid Monteiro Rodrigues, Rosiane de Freitas |
| contents | This work investigates structural and computational aspects of list-based graph coloring under interval constraints. Building on the framework of analogous and p-analogous problems, we show that classical List Coloring, $μ$-coloring, and $(γ,μ)$-coloring share strong complexity-preserving correspondences on graph classes closed under pendant-vertex extensions. These equivalences allow hardness and tractability results to transfer directly among the models. Motivated by applications in scheduling and resource allocation with bounded ranges, we introduce the interval-restricted $k$-$(γ,μ)$-coloring model, where each vertex receives an interval of exactly $k$ consecutive admissible colors. We prove that, although $(γ,μ)$-coloring is NP-complete even on several well-structured graph classes, its $k$-restricted version becomes polynomial-time solvable for any fixed $k$. Extending this formulation, we define $k$-$(γ,μ)$-choosability and analyze its expressive power and computational limits. Our results show that the number of admissible list assignments is drastically reduced under interval constraints, yielding a more tractable alternative to classical choosability, even though the general decision problem remains located at high levels of the polynomial hierarchy. Overall, the paper provides a unified view of list-coloring variants through structural reductions, establishes new complexity bounds for interval-based models, and highlights the algorithmic advantages of imposing fixed-size consecutive color ranges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_16807 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Analogy between List Coloring Problems and the Interval $k$-$(γ,μ)$-choosability property: theoretical aspects of complexity Gama, Simone Ingrid Monteiro Rodrigues, Rosiane de Freitas Computational Complexity This work investigates structural and computational aspects of list-based graph coloring under interval constraints. Building on the framework of analogous and p-analogous problems, we show that classical List Coloring, $μ$-coloring, and $(γ,μ)$-coloring share strong complexity-preserving correspondences on graph classes closed under pendant-vertex extensions. These equivalences allow hardness and tractability results to transfer directly among the models. Motivated by applications in scheduling and resource allocation with bounded ranges, we introduce the interval-restricted $k$-$(γ,μ)$-coloring model, where each vertex receives an interval of exactly $k$ consecutive admissible colors. We prove that, although $(γ,μ)$-coloring is NP-complete even on several well-structured graph classes, its $k$-restricted version becomes polynomial-time solvable for any fixed $k$. Extending this formulation, we define $k$-$(γ,μ)$-choosability and analyze its expressive power and computational limits. Our results show that the number of admissible list assignments is drastically reduced under interval constraints, yielding a more tractable alternative to classical choosability, even though the general decision problem remains located at high levels of the polynomial hierarchy. Overall, the paper provides a unified view of list-coloring variants through structural reductions, establishes new complexity bounds for interval-based models, and highlights the algorithmic advantages of imposing fixed-size consecutive color ranges. |
| title | Analogy between List Coloring Problems and the Interval $k$-$(γ,μ)$-choosability property: theoretical aspects of complexity |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2512.16807 |