Edge-coloring problems with forbidden patterns and planted colors
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917441298235392 |
|---|---|
| author | Barsukov, Alexey Mottet, Antoine Perinti, Davide |
| author_facet | Barsukov, Alexey Mottet, Antoine Perinti, Davide |
| contents | Edge-coloring problems with forbidden patterns are decision problems asking to find an edge-coloring of the input graph which avoids a homomorphism from a fixed forbidden family of edge-colored graphs. In the precolored version of these problems, some of the edges of the input graph are already colored, and the goal is to find an extension of this coloring which omits a homomorphism from a forbidden graph. The existence of a complexity classification for such problems is an open question of Bienvenu, ten Cate, Lutz, and Wolter (ACM TODS'14) and we answer it for certain forbidden families consisting of odd cycles and cliques. The proof consists of two main stages. First, we combine the techniques from infinite constraint satisfaction and finite Ramsey theory in order to show that the edge-coloring problem is poly-time equivalent to its precolored version. After that, we show that the precolored version is poly-time equivalent to a finite constraint satisfaction problem, which has a P vs.\ NP-complete dichotomy by the seminal results of Bulatov (FOCS'17) and Zhuk (FOCS'17). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_19000 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Edge-coloring problems with forbidden patterns and planted colors Barsukov, Alexey Mottet, Antoine Perinti, Davide Computational Complexity Discrete Mathematics 68R10 (Primary) 03B70, 05C15, 05C55, 08A70 (Secondary) F.2.2; G.2 Edge-coloring problems with forbidden patterns are decision problems asking to find an edge-coloring of the input graph which avoids a homomorphism from a fixed forbidden family of edge-colored graphs. In the precolored version of these problems, some of the edges of the input graph are already colored, and the goal is to find an extension of this coloring which omits a homomorphism from a forbidden graph. The existence of a complexity classification for such problems is an open question of Bienvenu, ten Cate, Lutz, and Wolter (ACM TODS'14) and we answer it for certain forbidden families consisting of odd cycles and cliques. The proof consists of two main stages. First, we combine the techniques from infinite constraint satisfaction and finite Ramsey theory in order to show that the edge-coloring problem is poly-time equivalent to its precolored version. After that, we show that the precolored version is poly-time equivalent to a finite constraint satisfaction problem, which has a P vs.\ NP-complete dichotomy by the seminal results of Bulatov (FOCS'17) and Zhuk (FOCS'17). |
| title | Edge-coloring problems with forbidden patterns and planted colors |
| topic | Computational Complexity Discrete Mathematics 68R10 (Primary) 03B70, 05C15, 05C55, 08A70 (Secondary) F.2.2; G.2 |
| url | https://arxiv.org/abs/2507.19000 |