I am wondering if the following relaxation of proper coloring appears somewhere. I have tried some searching and have found a few relaxations of proper coloring, but none the coincides with what I have below.

Let $G = (V,E)$ be a graph (or $H = (V, E)$ a hypergraph). Let $E = A_1 \uplus A_2 \uplus \cdots \uplus A_l$ be a partition. I am looking at coloring of the vertices such that for each $1 \leq i \leq l$ there exists some $e \in A_i$ where $e$ is not monochromatic. Notice we recover the standard notion of proper coloring by partitioning $E$ into singletons.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.