On 3-Coloring of $(2P_4,C_5)$-Free Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910293605482496 |
|---|---|
| author | Jelínek, Vít Klimošová, Tereza Masařík, Tomáš Novotná, Jana Pokorná, Aneta |
| author_facet | Jelínek, Vít Klimošová, Tereza Masařík, Tomáš Novotná, Jana Pokorná, Aneta |
| contents | The 3-coloring of hereditary graph classes has been a deeply-researched problem in the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden induced subgraphs $H_1,H_2,\ldots$; the graphs in the class are called $(H_1,H_2,\ldots)$-free. The complexity of 3-coloring is far from being understood, even for classes defined by a few small forbidden induced subgraphs. For $H$-free graphs, the complexity is settled for any $H$ on up to seven vertices. There are only two unsolved cases on eight vertices, namely $2P_4$ and $P_8$. For $P_8$-free graphs, some partial results are known, but to the best of our knowledge, $2P_4$-free graphs have not been explored yet. In this paper, we show that the 3-coloring problem is polynomial-time solvable on $(2P_4,C_5)$-free graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2011_06173 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | On 3-Coloring of $(2P_4,C_5)$-Free Graphs Jelínek, Vít Klimošová, Tereza Masařík, Tomáš Novotná, Jana Pokorná, Aneta Data Structures and Algorithms Discrete Mathematics Combinatorics 05C15, 05C85 The 3-coloring of hereditary graph classes has been a deeply-researched problem in the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden induced subgraphs $H_1,H_2,\ldots$; the graphs in the class are called $(H_1,H_2,\ldots)$-free. The complexity of 3-coloring is far from being understood, even for classes defined by a few small forbidden induced subgraphs. For $H$-free graphs, the complexity is settled for any $H$ on up to seven vertices. There are only two unsolved cases on eight vertices, namely $2P_4$ and $P_8$. For $P_8$-free graphs, some partial results are known, but to the best of our knowledge, $2P_4$-free graphs have not been explored yet. In this paper, we show that the 3-coloring problem is polynomial-time solvable on $(2P_4,C_5)$-free graphs. |
| title | On 3-Coloring of $(2P_4,C_5)$-Free Graphs |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics 05C15, 05C85 |
| url | https://arxiv.org/abs/2011.06173 |