Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm

DVORAK, Zdenek; Daniel KRÁĽ a Robin THOMAS. Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm. Journal of Combinatorial Theory. Series B. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2022, roč. 152, January, s. 483-504. ISSN 0095-8956. Dostupné z: https://doi.org/10.1016/j.jctb.2021.07.002.

Základní údaje

Originální název

Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm

Autoři

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

Vydání

Journal of Combinatorial Theory. Series B, SAN DIEGO, ACADEMIC PRESS INC ELSEVIER SCIENCE, 2022, 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.400

Kód RIV

RIV/00216224:14330/22:00127781

Organizační jednotka

Fakulta informatiky

DOI

https://doi.org/10.1016/j.jctb.2021.07.002

UT WoS

000722420800007

EID Scopus

2-s2.0-85111273491

Klíčová slova anglicky

Coloring; Surfaces; Triangle-free

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

We give a linear-time algorithm to decide 3-colorability of a triangle-free graph embedded in a fixed surface, and a quadratic-time algorithm to output a 3-coloring in the affirmative case. The algorithms also allow to prescribe the coloring of a bounded number of vertices.