On 3-Coloring of (2P_4, C_5)-Free Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455152" target="_blank" >RIV/00216208:11320/22:10455152 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=JXoCs5kacN" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=JXoCs5kacN</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00453-022-00937-9" target="_blank" >10.1007/s00453-022-00937-9</a>
Alternative languages
Result language
angličtina
Original language name
On 3-Coloring of (2P_4, C_5)-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 H_1, H_2, ...; the graphs in the class are called (H_1, H_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 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
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
2022
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
Name of the periodical
Algorithmica
ISSN
0178-4617
e-ISSN
1432-0541
Volume of the periodical
84
Issue of the periodical within the volume
6
Country of publishing house
US - UNITED STATES
Number of pages
22
Pages from-to
1526-1547
UT code for WoS article
000755415600002
EID of the result in the Scopus database
2-s2.0-85124764026