Constricting the Computational Complexity Gap of the $4$-Coloring Problem in $(P_t,C_3)$-free Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915475096600576 |
|---|---|
| author | Jaworska, Justyna Kielak, Bartłomiej Masařík, Tomáš Masaříková, Jana |
| author_facet | Jaworska, Justyna Kielak, Bartłomiej Masařík, Tomáš Masaříková, Jana |
| contents | The $k$-Coloring problem on hereditary graph classes has been a deeply researched problem over the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden induced subgraphs. We say that a graph is $(H_1,H_2,\ldots)$-free if it does not contain any of $H_1,H_2,\ldots$ as induced subgraphs. The complexity landscape of the problem remains unclear even when restricting to the case $k=4$ and classes defined by a few forbidden induced subgraphs. While the case of only one forbidden induced subgraph has been completely resolved lately, the complexity when considering two forbidden induced subgraphs still has a couple of unknown cases. In particular, $4$-Coloring on $(P_6,C_3)$-free graphs is polynomial while it is NP-hard on $(P_{22},C_3)$-free graphs.
We provide a reduction showing NP-completeness of $4$-Coloring on $(P_t,C_3)$-free graphs for $19\leq t\leq 21$, thus constricting the gap of cases whose complexity remains unknown. Our proof includes a computer search ensuring that the graph family obtained through the reduction is indeed $P_{19}$-free. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02423 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constricting the Computational Complexity Gap of the $4$-Coloring Problem in $(P_t,C_3)$-free Graphs Jaworska, Justyna Kielak, Bartłomiej Masařík, Tomáš Masaříková, Jana Computational Complexity Discrete Mathematics Combinatorics 05C15, 05C85 The $k$-Coloring problem on hereditary graph classes has been a deeply researched problem over the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden induced subgraphs. We say that a graph is $(H_1,H_2,\ldots)$-free if it does not contain any of $H_1,H_2,\ldots$ as induced subgraphs. The complexity landscape of the problem remains unclear even when restricting to the case $k=4$ and classes defined by a few forbidden induced subgraphs. While the case of only one forbidden induced subgraph has been completely resolved lately, the complexity when considering two forbidden induced subgraphs still has a couple of unknown cases. In particular, $4$-Coloring on $(P_6,C_3)$-free graphs is polynomial while it is NP-hard on $(P_{22},C_3)$-free graphs. We provide a reduction showing NP-completeness of $4$-Coloring on $(P_t,C_3)$-free graphs for $19\leq t\leq 21$, thus constricting the gap of cases whose complexity remains unknown. Our proof includes a computer search ensuring that the graph family obtained through the reduction is indeed $P_{19}$-free. |
| title | Constricting the Computational Complexity Gap of the $4$-Coloring Problem in $(P_t,C_3)$-free Graphs |
| topic | Computational Complexity Discrete Mathematics Combinatorics 05C15, 05C85 |
| url | https://arxiv.org/abs/2509.02423 |