Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs
2015
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
12
References
2
Citations
NaN
KQI