Přejít k obsahu


3-coloring triangle-free planar graphs with a precolored 9-cycle

Citace:
CHOI, I., EKSTEIN, J., HOLUB, P., LIDICKÝ, B. 3-coloring triangle-free planar graphs with a precolored 9-cycle. EUROPEAN JOURNAL OF COMBINATORICS, 2018, roč. 68, č. February, s. 38-65. ISSN: 0195-6698
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: 3-coloring triangle-free planar graphs with a precolored 9-cycle
Rok vydání: 2018
Autoři: Ilkyoo Choi , RNDr. Jan Ekstein Ph.D. , Doc. RNDr. Přemysl Holub Ph.D. , Bernard Lidický
Abstrakt CZ: Pro daný rovinný graf bez trojúhelníků G a 9-cyklus C v G charakterizujeme situace, kdy 3-obarvení C nelze rozšířit na vlastní 3-obarvení G. Tento výsledek rozšiřuje předchozí výsledky pro cykly C délky nejvýše 8.
Abstrakt EN: Given a triangle-free planar graph G and a 9-cycle C in G, we characterize situations where a 3-coloring of C does not extend to a proper 3-coloring of G. This extends previous results when C is a cycle of length at most 8.
Klíčová slova

Zpět

Patička