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⩾1g⩾1. This upper bound became known as the Heawood number H(g)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)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⩾1g⩾1 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 ΣΣ. More precisely, we determine the number H2(Σ)H2(Σ) such that if a graph G   embedded on ΣΣ is the edge disjoint union of two graphs G1G1 and G2G2, thenω(G1)+ω(G2)⩽χ(G1)+χ(G2)⩽H2(Σ).ω(G1)+ω(G2)⩽χ(G1)+χ(G2)⩽H2(Σ).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 ΣΣ.