Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs

Abstract Given graphs G and H , a vertex coloring c : V ( G ) → N is an H -free coloring of G if no color class contains a subgraph isomorphic to H . The H -free chromatic number of G , χ ( H , G ) , is the minimum number of colors in an H -free coloring of G . The H -free chromatic sum of G , Σ ( H , G ) , is the minimum value achieved by summing the vertex colors of each H -free coloring of G . We provide a general bound for Σ ( H , G ) , discuss the computational complexity of finding this parameter for different choices of H , and prove an exact formulas for some graphs G . For every integer k and for every graph H , we construct families of graphs, G k with the property that k more colors than χ ( H , G ) are required to realize Σ ( H , G ) for H -free colorings. More complexity results and constructions of graphs requiring extra colors are given for planar and outerplanar graphs.