Extending partial 5-colorings and 6-colorings in planar graphs

KRÁĽ, Daniel. Extending partial 5-colorings and 6-colorings in planar graphs. JOURNAL OF COMBINATORIAL THEORY SERIES B. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2006, roč. 96, č. 1, s. 100-110. ISSN 0095-8956. Dostupné z: https://doi.org/10.1016/j.jctb.2005.06.006.

Základní údaje

Originální název

Extending partial 5-colorings and 6-colorings in planar graphs

Autoři

KRÁĽ, Daniel

Vydání

JOURNAL OF COMBINATORIAL THEORY SERIES B, SAN DIEGO, ACADEMIC PRESS INC ELSEVIER SCIENCE, 2006, 0095-8956

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

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

Impakt faktor

Impact factor: 0.792

DOI

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

UT WoS

000234006600007

Klíčová slova anglicky

extension of graph colorings; coloring of planar graphs

---

Anotace

V originále

Let D be a disc and let X be a finite set of points on the boundary of D. A set C of k-colorings of the points X is called k-feasible if there exists a plane graph G drawn in the disc D with X subset of V(G) such that precisely colorings contained in the set C can be extended to proper k-colorings of G. We show that for each k-feasible set C, there exists such a plane graph G of order at most vertical bar X vertical bar + 5 vertical bar(X vertical bar) if k = 5 and 17 vertical bar X vertical bar - 48 if k = 6. (c) 2005 Elsevier Inc. All rights reserved.