Graph coloring with no large monochromatic components

Abstract

(This paper is an extended abstract) For a graph G, we define mcc(t,G) as the smallest m such that there is a coloring of V(G) by t colors so that no monochromatic connected subgraph of G has more than m vertices. For various graph classes we investitgate the maximum of mcc(2,G) over all n-vertex graphs in the class.

In particular, for the class of all planar graphs this maximum is of order n to 2/3.

Keywords

• Graph
• coloring
• large
• monochromatic
• components