k-CHROMATIC NUMBER OF GRAPHS ON SURFACES

摘要

A well-known result (Heawood [Quart. J. Pure Appl. Math., 24 (1890), pp. 332-338], Ringel [Map Color Theorem, Springer-Verlag, New York, 1974], Ringel and Youngs [Proc. Nat. Acad. Sci., U.S.A., 60 (1968), pp. 438-445]) states that the maximum chromatic number of a graph embedded in a given surface S coincides with the size of the largest clique that can be embedded in S, and that this number can be expressed as a simple formula in the Euler genus of S. A partition of a graph G into k parts consists of k edge-disjoint subgraphs G_1,..., G_k such that E(G) = E(G_1) U E(G_2) ∪... ∪ E(G_k). The k-chromatic number _(xk)(G) is the maximum of Σ~k_(i=1) x(G_i) over all partitions of G into k parts. We derive a Heawood-type formula for the k-chromatic number of graphs embedded in a fixed surface, improving the previously known upper bounds. In infinitely many cases, the new upper bound coincides with the lower bound obtained from embedding disjoint cliques in the surface. In the proof of this result, we derive a variant of Euler's formula for the union of several graphs that might be interesting independently.