Colorings avoiding monochromatic subgraphs- minimizing sum of colors

Ewa Kubicka
University of Louisville

Grzegorz Kubicki
University of Louisville, USA, and University of Opole, Poland

Kathleen McKeon
Connecticut College



Content: Given graphs $G$ and $H$, a vertex coloring $c:V(G) \rightarrow \mathbb{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$, $\chi(H,G)$, is the minimum number of colors in an $H$-free coloring of $G$. The $H$-free chromatic sum of $G$, $\Sigma(H,G)$, is the minimum value achieved by summing the vertex colors of each $H$-free coloring of $G$. We discuss the computational complexity of finding this parameter for different choices of $H$ and prove 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 $\chi(H,G)$ are required to realize $\Sigma(H,G)$ for $H$-free colorings. More complexity results and constructions of graphs requiring extra colors are given for planar and outerplanar graphs.

Back to all abstracts