3-Coloring C4 or C3 -Free Diameter Two Graphs
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10476387" target="_blank" >RIV/00216208:11320/23:10476387 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1007/978-3-031-38906-1_36" target="_blank" >https://doi.org/10.1007/978-3-031-38906-1_36</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-38906-1_36" target="_blank" >10.1007/978-3-031-38906-1_36</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
3-Coloring C4 or C3 -Free Diameter Two Graphs
Popis výsledku v původním jazyce
The question whether 3-Coloring can be solved in polynomial time for the diameter two graphs is a well-known open problem in the area of algorithmic graph theory. We study the problem restricted to graph classes that avoid cycles of given lengths as induced subgraphs. Martin et al. [CIAC 2021] showed that the problem is solvable in polynomial time for C5 -free or C6 -free graphs, and, (C4, Cs) -free graphs where sELEMENT OF { 3, 7, 8, 9 }. We extend their result proving that it is polynomial-time solvable for (C4, Cs) -free graphs, for any constant s>= 5, and for (C3, C7) -free graphs. Our results also hold for the more general problem List 3-Colouring.
Název v anglickém jazyce
3-Coloring C4 or C3 -Free Diameter Two Graphs
Popis výsledku anglicky
The question whether 3-Coloring can be solved in polynomial time for the diameter two graphs is a well-known open problem in the area of algorithmic graph theory. We study the problem restricted to graph classes that avoid cycles of given lengths as induced subgraphs. Martin et al. [CIAC 2021] showed that the problem is solvable in polynomial time for C5 -free or C6 -free graphs, and, (C4, Cs) -free graphs where sELEMENT OF { 3, 7, 8, 9 }. We extend their result proving that it is polynomial-time solvable for (C4, Cs) -free graphs, for any constant s>= 5, and for (C3, C7) -free graphs. Our results also hold for the more general problem List 3-Colouring.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA22-19073S" target="_blank" >GA22-19073S: Kombinatorická a výpočetní složitost v topologii a geometrii</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2023
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISBN
978-3-031-38905-4
ISSN
—
e-ISSN
1611-3349
Počet stran výsledku
14
Strana od-do
547-560
Název nakladatele
SPRINGER
Místo vydání
Neuveden
Místo konání akce
Montreal, Canada
Datum konání akce
31. 7. 2023
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—