3-Coloring C4 or C3 -Free Diameter Two Graphs

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

3-Coloring C4 or C3 -Free Diameter Two Graphs

Original language description

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&gt;= 5, and for (C3, C7) -free graphs. Our results also hold for the more general problem List 3-Colouring.

Czech name

—

Czech description

—

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)

Project

<a href="/en/project/GA22-19073S" target="_blank" >GA22-19073S: Combinatorial and computational complexity in topology and geometry</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

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

Number of pages

14

Pages from-to

547-560

Publisher name

SPRINGER

Place of publication

Neuveden

Event location

Montreal, Canada

Event date

Jul 31, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—