Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations

DVORAK, Zdenek; Daniel KRÁĽ and Robin THOMAS. Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations. Journal of Combinatorial Theory. Series B. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2024, vol. 164, No 1, p. 517-548. ISSN 0095-8956. Available from: https://dx.doi.org/10.1016/j.jctb.2023.11.001.

Basic information

Original name

Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations

Authors

DVORAK, Zdenek; Daniel KRÁĽ (203 Czech Republic, guarantor, belonging to the institution) and Robin THOMAS

Edition

Journal of Combinatorial Theory. Series B, SAN DIEGO, ACADEMIC PRESS INC ELSEVIER SCIENCE, 2024, 0095-8956

---

Other information

Language

English

Type of outcome

Article in a journal

Field of Study

10101 Pure mathematics

Country of publisher

Netherlands

Confidentiality degree

is not subject to a state or trade secret

References:

URL

Impact factor

Impact factor: 1.200 in 2023

RIV identification code

RIV/00216224:14330/24:00135718

Organization unit

Faculty of Informatics

DOI

http://dx.doi.org/10.1016/j.jctb.2023.11.001

UT WoS

001129843300001

EID Scopus

2-s2.0-85177028556

Keywords in English

Coloring; Surfaces; Quadrangulations

Tags

International impact, Reviewed

---

Abstract

In the original language

We give a linear-time algorithm to decide 3-colorability (and find a 3-coloring, if it exists) of quadrangulations of a fixed surface. The algorithm also allows to prescribe the coloring for a bounded number of vertices.(c) 2023 Elsevier Inc. All rights reserved.