A map colour theorem for the union of graphs

摘要

In 1890 Heawood [Map colour theorem, Quart. J. Pure Appl. Math. 24 (1890) 332-338] established an upper bound for the chromatic number of a graph embedded on a surface of Euler genus g >= 1. This upper bound became known as the Heawood number H(g). Almost a century later, Ringel [Map Color Theorem, Springer, New York, 1974] and Ringel and Youngs [Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. USA 60 (1968) 438-445] proved that the Heawood number H(g) is in fact the maximum chromatic number as well as the maximum clique number of graphs embedded on a surface of Euler genus g >= I besides the Klein bottle. In this paper, we present a Heawood-type formula for the edge disjoint union of two graphs that are embedded on a given surface Sigma. More precisely, we determine the number H-2(Sigma) such that if a graph G embedded on Sigma is the edge disjoint union of two graphs G(1) and G(2), then omega(G(1)) + omega(G(2)) <= chi(G(1)) + chi(G(2)) <= H-2(Sigma). Similar to the results of Ringel and Ringel and Youngs, we show that this bound is sharp for all but at most one non-orientable surface Sigma. (c) 2005 Elsevier Inc. All rights reserved.