On the structure of ($4K_1$, $C_4$, $P_6$)-free graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918222278688768 |
|---|---|
| author | Hoàng, Chính T. Javadi, Ramin Trotignon, Nicolas |
| author_facet | Hoàng, Chính T. Javadi, Ramin Trotignon, Nicolas |
| contents | Determining the complexity of colouring ($4K_1, C_4$)-free graph is a long open problem. Recently Penev showed that there is a polynomial-time algorithm to colour a ($4K_1, C_4, C_6$)-free graph. In this paper, we will prove that if $G$ is a ($4K_1, C_4, P_6$)-free graph that contains a $C_6$, then $G$ has bounded clique-width. To this purpose, we use a new method to bound the clique-width, that is of independent interest. As a consequence, there is a polynomial-time algorithm to colour ($4K_1, C_4, P_6$)-free graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_23195 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the structure of ($4K_1$, $C_4$, $P_6$)-free graphs Hoàng, Chính T. Javadi, Ramin Trotignon, Nicolas Discrete Mathematics Combinatorics 05C15, 05C75 Determining the complexity of colouring ($4K_1, C_4$)-free graph is a long open problem. Recently Penev showed that there is a polynomial-time algorithm to colour a ($4K_1, C_4, C_6$)-free graph. In this paper, we will prove that if $G$ is a ($4K_1, C_4, P_6$)-free graph that contains a $C_6$, then $G$ has bounded clique-width. To this purpose, we use a new method to bound the clique-width, that is of independent interest. As a consequence, there is a polynomial-time algorithm to colour ($4K_1, C_4, P_6$)-free graphs. |
| title | On the structure of ($4K_1$, $C_4$, $P_6$)-free graphs |
| topic | Discrete Mathematics Combinatorics 05C15, 05C75 |
| url | https://arxiv.org/abs/2511.23195 |