Coloring face hypergraphs on surfaces

DVORAK, Z; Daniel KRÁĽ a R SKREKOVSKI. Coloring face hypergraphs on surfaces. European Journal of Combinatorics. LONDON: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2005, roč. 26, č. 1, s. 95-110. ISSN 0195-6698. Dostupné z: https://doi.org/10.1016/j.ejc.2004.01.003.

Základní údaje

Originální název

Coloring face hypergraphs on surfaces

Autoři

DVORAK, Z; Daniel KRÁĽ a R SKREKOVSKI

Vydání

European Journal of Combinatorics, LONDON, ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2005, 0195-6698

---

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.320

DOI

https://doi.org/10.1016/j.ejc.2004.01.003

UT WoS

000225382200007

---

Anotace

V originále

The face hypergraph of a graph G embedded on a surface has the same vertex set as G and its edges are the sets of vertices forming faces of G. A hypergraph is k-choosable if for each assignment of lists of colors of sizes k to its vertices, there is a coloring of the vertices from these lists avoiding a monochromatic edge. We prove that the face hypergraph of the triangulation of a surface of Euler genus g is O((3)rootg)-choosable. This bound matches a previously known lower bound of order Omega((3)rootg). If each face of the graph is incident with at least r distinct vertices, then the face hypergraph is also O( (r)rootg)-choosable. Note that colorings of face hypergraphs for r = 2 correspond to usual vertex colorings and the upper bound O(rootg) thus follows from Heawood's formula. Separate results for small genera are presented: the bound 3 for triangulations of the surface of Euler genus g = 3 and the bound [7 + root36g + 49/6] for 6 surfaces of Euler genus g greater than or equal to 3. Our results dominate the previously known bounds for all genera except for g = 4, 7, 8, 9. 14. (C) 2004 Elsevier Ltd. All rights reserved.