Charles Explorer logo
🇨🇿

3-Coloring C4 or C3 -Free Diameter Two Graphs

Publikace na Matematicko-fyzikální fakulta |
2023

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

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.