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

DVORAK, Zdenek; Daniel KRÁĽ a 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, roč. 164, č. 1, s. 517-548. ISSN 0095-8956. Dostupné z: https://dx.doi.org/10.1016/j.jctb.2023.11.001.

Základní údaje

Originální název

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

Autoři

DVORAK, Zdenek; Daniel KRÁĽ (203 Česká republika, garant, domácí) a Robin THOMAS

Vydání

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

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 1.200 v roce 2023

Kód RIV

RIV/00216224:14330/24:00135718

Organizační jednotka

Fakulta informatiky

DOI

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

UT WoS

001129843300001

EID Scopus

2-s2.0-85177028556

Klíčová slova anglicky

Coloring; Surfaces; Quadrangulations

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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.