On 3-Coloring of (2P4, C5)-Free Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10436736" target="_blank" >RIV/00216208:11320/21:10436736 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/978-3-030-86838-3_30" target="_blank" >https://doi.org/10.1007/978-3-030-86838-3_30</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-86838-3_30" target="_blank" >10.1007/978-3-030-86838-3_30</a>
Alternative languages
Result language
angličtina
Original language name
On 3-Coloring of (2P4, C5)-Free Graphs
Original language description
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 H1, H2, ... ; the graphs in the class are called (H1, H2, ... )-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 2 P4 and P8. For P8 -free graphs, some partial results are known, but to the best of our knowledge, 2P4 -free graphs have not been explored yet. In this paper, we show that the 3-coloring problem is polynomial-time solvable on (2P4, C5) -free graphs.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Graph-Theoretic Concepts in Computer Science
ISBN
978-3-030-86837-6
ISSN
0302-9743
e-ISSN
1611-3349
Number of pages
14
Pages from-to
388-401
Publisher name
Springer Nature
Place of publication
Neuveden
Event location
Varšava
Event date
Jun 23, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—