Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs

DVOŘÁK, Zdeněk; Daniel KRÁĽ a Robin THOMAS. Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs. Journal of Combinatorial Theory. Series B. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2021, roč. 150, September 2021, s. 270-304. ISSN 0095-8956. Dostupné z: https://doi.org/10.1016/j.jctb.2020.09.001.

Základní údaje

Originální název

Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs

Autoři

DVOŘÁK, Zdeněk; Daniel KRÁĽ a Robin THOMAS

Vydání

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

Nizozemské království

Utajení

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

Odkazy

URL

Impakt faktor

Impact factor: 1.491

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/21:00124668

Organizační jednotka

Fakulta informatiky

DOI

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

UT WoS

000670294100009

EID Scopus

2-s2.0-85090866217

Klíčová slova anglicky

Graph coloring; Graphs on surfaces; Triangle-free

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

Let G be a 4-critical graph with t triangles, embedded in a surface of genus g. Let c be the number of 4-cycles in G that do not bound a 2-cell face. We prove that 1] f face of G (|f| & minus; 4) <= kappa(g +t + c & minus; 1) for a fixed constant kappa, thus generalizing and strengthening several known results. As a corollary, we prove that every triangle-free graph G embedded in a surface of genus g contains a set of O(g) vertices such that G & minus; X is 3-colorable. (c) 2020 Elsevier Inc. All rights reserved.