Colouring $(P_r+P_s)$-Free Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2018
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911454507040768 |
|---|---|
| author | Klimošová, Tereza Malík, Josef Masařík, Tomáš Novotná, Jana Paulusma, Daniël Slívová, Veronika |
| author_facet | Klimošová, Tereza Malík, Josef Masařík, Tomáš Novotná, Jana Paulusma, Daniël Slívová, Veronika |
| contents | The $k$-Colouring problem is to decide if the vertices of a graph can be coloured with at most $k$ colours for a fixed integer $k$ such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list $L(u) \subseteq \{1,\cdots, k\}$, then we obtain the List $k$-Colouring problem. A graph $G$ is $H$-free if $G$ does not contain $H$ as an induced subgraph. We continue an extensive study into the complexity of these two problems for $H$-free graphs. The graph $P_r+P_s$ is the disjoint union of the $r$-vertex path $P_r$ and the $s$-vertex path $P_s$. We prove that List $3$-Colouring is polynomial-time solvable for $(P_2+P_5)$-free graphs and for $(P_3+P_4)$-free graphs. Combining our results with known results yields complete complexity classifications of $3$-Colouring and List $3$-Colouring on $H$-free graphs for all graphs $H$ up to seven vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1804_11091 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Colouring $(P_r+P_s)$-Free Graphs Klimošová, Tereza Malík, Josef Masařík, Tomáš Novotná, Jana Paulusma, Daniël Slívová, Veronika Data Structures and Algorithms Computational Complexity The $k$-Colouring problem is to decide if the vertices of a graph can be coloured with at most $k$ colours for a fixed integer $k$ such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list $L(u) \subseteq \{1,\cdots, k\}$, then we obtain the List $k$-Colouring problem. A graph $G$ is $H$-free if $G$ does not contain $H$ as an induced subgraph. We continue an extensive study into the complexity of these two problems for $H$-free graphs. The graph $P_r+P_s$ is the disjoint union of the $r$-vertex path $P_r$ and the $s$-vertex path $P_s$. We prove that List $3$-Colouring is polynomial-time solvable for $(P_2+P_5)$-free graphs and for $(P_3+P_4)$-free graphs. Combining our results with known results yields complete complexity classifications of $3$-Colouring and List $3$-Colouring on $H$-free graphs for all graphs $H$ up to seven vertices. |
| title | Colouring $(P_r+P_s)$-Free Graphs |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/1804.11091 |