The bounded chromatic number for graphs of genus g

AbstractFor G a collection of finite graphs, the bounded chromatic number χB(G) is the smallest number of colors c for which there exists an integer N such that every graph G∈G can be vertex c-colored without forcing more than N monochromatic edges. The bounded (simple) path chromatic number χP(G) (χSP(G)) is the smallest number of colors c for which there exists an integer N such that every graph G∈G can be c-colored without forcing a monochromatic (simple) path of length more than N. For the set Sg of all graphs of genus g it is known that 4≤χB(Sg)≤6, and χSP(Sg)=4. In this paper we show that χB(Sg)≤5, and χP(Sg)=4. For g≥1, let μ5(g) (π4(g)) denote the smallest integer x such that every graph G∈Sg can be 5-colored without forcing more than x monochromatic edges (4-colored without forcing a monochromatic path of length more than x). We also show that 2g ≤ μ5(g) ≤ 74g − 36 and (38)g − (12) 3g + 332 ≤ π4(g) ≤ 224g − 106