Three-coloring triangle-free graphs on surfaces III. Graphs of girth five

DVORAK, Zdeněk; Daniel KRÁĽ a Robin THOMAS. Three-coloring triangle-free graphs on surfaces III. Graphs of girth five. Journal of Combinatorial Theory. Series B. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2020, roč. 145, November 2020, s. 376-432. ISSN 0095-8956. Dostupné z: https://doi.org/10.1016/j.jctb.2020.06.005.

Základní údaje

Originální název

Three-coloring triangle-free graphs on surfaces III. Graphs of girth five

Autoři

DVORAK, Zdeněk; Daniel KRÁĽ a Robin THOMAS

Vydání

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

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Odkazy

URL

Impakt faktor

Impact factor: 1.317

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/20:00116811

Organizační jednotka

Fakulta informatiky

DOI

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

UT WoS

000575863900014

EID Scopus

2-s2.0-85087299067

Klíčová slova anglicky

Coloring; Triangle-free; Surfaces

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

We show that the size of a 4-critical graph of girth at least five is bounded by a linear function of its genus. This strengthens the previous bound on the size of such graphs given by Thomassen. It also serves as the basic case for the description of the structure of 4-critical triangle-free graphs embedded in a fixed surface, presented in a future paper of this series. (C) 2020 Elsevier Inc. All rights reserved.