Universität zu Köln

Bonomo-Braberman, Flavia, Chudnovsky, Maria, Goedgebeur, Jan ORCID: 0000-0001-8984-2463, Maceli, Peter, Schaudt, Oliver, Stein, Maya and Zhong, Mingxian ORCID: 0000-0001-5924-1296 (2021). Better 3-coloring algorithms: Excluding a triangle and a seven vertex path. Theor. Comput. Sci., 850. S. 98 - 116. AMSTERDAM: ELSEVIER. ISSN 1879-2294

Full text not available from this repository.

Abstract

We present an algorithm to color a graph G with no triangle and no induced 7-vertex path (i.e., a {P-7, C-3}-free graph), where every vertex is assigned a list of possible colors which is a subset of {1, 2, 3}. While this is a special case of the problem solved in Bonomo et al. (2018) [1], that does not require the absence of triangles, the algorithm here is both faster and conceptually simpler. The complexity of the algorithm is O(vertical bar V (G)vertical bar(5)(vertical bar V (G)vertical bar + vertical bar E(G)vertical bar)), and if G is bipartite, it improves to O(vertical bar V (G)vertical bar(2)(vertical bar V (G)vertical bar + vertical bar E(G)vertical bar)). Moreover, we prove that there are finitely many minimal obstructions to list 3-coloring {P-t, C-3}-free graphs if and only if t <= 7. This implies the existence of a polynomial time certifying algorithm for list 3-coloring in {P-7, C-3}-free graphs. We furthermore determine other cases of t, l, and k such that the family of minimal obstructions to list k-coloring in {P-t, C-l}-free graphs is finite. (C) 2020 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Bonomo-Braberman, Flavia UNSPECIFIED UNSPECIFIED UNSPECIFIED Chudnovsky, Maria UNSPECIFIED UNSPECIFIED UNSPECIFIED Goedgebeur, Jan UNSPECIFIED orcid.org/0000-0001-8984-2463 UNSPECIFIED Maceli, Peter UNSPECIFIED UNSPECIFIED UNSPECIFIED Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED Stein, Maya UNSPECIFIED UNSPECIFIED UNSPECIFIED Zhong, Mingxian UNSPECIFIED orcid.org/0000-0001-5924-1296 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-598092
DOI:	10.1016/j.tcs.2020.10.032
Journal or Publication Title:	Theor. Comput. Sci.
Volume:	850
Page Range:	S. 98 - 116
Date:	2021
Publisher:	ELSEVIER
Place of Publication:	AMSTERDAM
ISSN:	1879-2294
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language Computer Science, Theory & Methods Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/59809