Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętyOn 3-Coloring of (2P_4,C_4)-Free Graphs
| cris.lastimport.scopus | 2024-02-12T20:24:16Z |
| dc.abstract.en | 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 1, 2,…; the graphs in the class are called (1, 2,…)-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 24 and 8. For 8-free graphs, some partial results are known, but to the best of our knowledge, 24-free graphs have not been explored yet. In this paper, we show that the 3-coloring problem is polynomial-time solvable on (24,5)-free graphs. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.conference.country | Polska |
| dc.conference.datefinish | 2021-06-25 |
| dc.conference.datestart | 2021-06-23 |
| dc.conference.place | Warszawa |
| dc.conference.series | International Workshop on Graph-Theoretic Concepts in Computer Science |
| dc.conference.series | International Workshop on Graph-Theoretic Concepts in Computer Science |
| dc.conference.seriesshortcut | WG |
| dc.conference.shortcut | WG 2021 |
| dc.conference.weblink | https://sin.put.poznan.pl/conferences/details/conference/47th-international-workshop-on-graph-theoretic-concepts-in-computer-science-wg-2021 |
| dc.contributor.author | Klimošová, Tereza |
| dc.contributor.author | Masařik, Tomáš |
| dc.contributor.author | Jelínek, Vít |
| dc.contributor.author | Pokorná, Aneta |
| dc.contributor.author | Masaříková, Jana |
| dc.date.accessioned | 2024-01-25T15:44:39Z |
| dc.date.available | 2024-01-25T15:44:39Z |
| dc.date.issued | 2021 |
| dc.description.finance | Publikacja bezkosztowa |
| dc.description.volume | 12911 |
| dc.identifier.doi | 10.1007/978-3-030-86838-3_30 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/114639 |
| dc.identifier.weblink | https://doi.org/10.1007/978-3-030-86838-3\_30 |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.pages | 388--401 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.title | On 3-Coloring of (2P_4,C_4)-Free Graphs |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |