On 3-colorability of (claw, diamond)-free graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912885883535360 |
|---|---|
| author | Hodur, Nadzieja Pilśniak, Monika Prorok, Magdalena Schiermeyer, Ingo |
| author_facet | Hodur, Nadzieja Pilśniak, Monika Prorok, Magdalena Schiermeyer, Ingo |
| contents | The $3$-colorability problem is a well-known NP-complete problem and it remains NP-complete for $(claw, diamond, K_4)$-free graphs. Recently, $3$-colorability has been also considered for $(claw, N_{1,1,1})$-free graphs. Here, a generalised net $N_{i, j, k}$ is the graph obtained by identifying each vertex of a triangle with an endvertex of one of three vetex-disjont paths of lengths $i, j, k$.
We study the class of $(claw, diamond, N_{i, j, k})$-free graphs for $(i, j, k) \in \{(1, 1, 3),$ $ (1, 2, 2), $ $(2, 2, 2) \}$. We show that these graphs are $3$-colorable or contain a $K_4$ or belong to some well-defined class of non $3$-colorable graphs. Moreover, we prove that there are only finitely many non $3$-colorable $N_{1, 2, k}$-free graphs for any $k \geq 2$, but there exist infinitely many non $3$-colorable $N_{i, j, k}$-free graphs for any
$2 \leq i \leq j \leq k.$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_07229 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On 3-colorability of (claw, diamond)-free graphs Hodur, Nadzieja Pilśniak, Monika Prorok, Magdalena Schiermeyer, Ingo Combinatorics 05C15, 05C17, 68Q25, 68W40 The $3$-colorability problem is a well-known NP-complete problem and it remains NP-complete for $(claw, diamond, K_4)$-free graphs. Recently, $3$-colorability has been also considered for $(claw, N_{1,1,1})$-free graphs. Here, a generalised net $N_{i, j, k}$ is the graph obtained by identifying each vertex of a triangle with an endvertex of one of three vetex-disjont paths of lengths $i, j, k$. We study the class of $(claw, diamond, N_{i, j, k})$-free graphs for $(i, j, k) \in \{(1, 1, 3),$ $ (1, 2, 2), $ $(2, 2, 2) \}$. We show that these graphs are $3$-colorable or contain a $K_4$ or belong to some well-defined class of non $3$-colorable graphs. Moreover, we prove that there are only finitely many non $3$-colorable $N_{1, 2, k}$-free graphs for any $k \geq 2$, but there exist infinitely many non $3$-colorable $N_{i, j, k}$-free graphs for any $2 \leq i \leq j \leq k.$ |
| title | On 3-colorability of (claw, diamond)-free graphs |
| topic | Combinatorics 05C15, 05C17, 68Q25, 68W40 |
| url | https://arxiv.org/abs/2602.07229 |