Cycle-Compelling Colorings of Graphs

We define a cycle-compelling coloring of a graph as a proper coloring of the vertices such that every subgraph induced by one vertex of each color contains a cycle. The cycle-compelling number is defined to be the minimum k such that some k-coloring is cycle-compelling. We provide some general bounds and algorithmic results on this and related parameters. We also investigate the value in specific graph families including cubic graphs, disjoint union of cliques, and outerplanar graphs.