Chromatic sums for colorings avoiding monochromatic subgraphs
Ewa Kubicka, Grzegorz Kubicki, Kathleen A. McKeon · Discussiones Mathematicae Graph Theory · 2015
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.