Modification of graph coloring

Question

I thought some modification of graph coloring.

Let $G=(V,E)$ be a simple graph.

Define a map $\phi: V\rightarrow [n]=\{1,2,\cdots,n\}$ satisfying

• for any cycle $C$ in $G$, $|\phi^{-1}(k)\cap V(C)| \leq \frac{1}{2}|V(C)|$ for any $k\in[n]$.

(i.e., for any color $k$, it cannot occupy more than half ratio of vertices of any cycles in $G$.)

Then, I call it 'half-cycle $n$-coloring', and define $\chi_h(G)$ as the minimum number $n$, which above half-cycle $n$-coloring exists.

It is easy to verify that

• $\chi_h(G) \leq \chi(G)$

since $n$-coloring is also half-cycle $n$-coloring.

I checked that $\chi_h(G)=\chi(G)$ for $G=K_n$ or $C_n$, $n\geq 3$, and for some other simple graphs. For a tree $T$ with at least one edge, $\chi_h(T)=1 < 2 = \chi(T)$. And I couldn't find '2-connected' graph $G$, which makes above inequality is strict.

I wonder an example that such inequality is strict. Or, does it hold for any 2-connected graph? (if so, it is very interesting!)

Answer 1

When $\chi_h(G) \ge 2$, we have $\chi(G) = \chi_h(G)$.

If the half-cycle coloring of a graph $G$ has at least $2$ colors, then we can transform it into a proper coloring by repeating the following procedure:

1. Pick two colors $i$ and $j$. Let $G_{ij}$ be the subgraph induced by vertices of those two colors.
2. Observe that in any odd cycle of length $2k+1$ in $G$, at most $k$ vertices have color $i$ and at most $k$ more have color $j$. Therefore the odd cycle does not remain in $G_{ij}$. This is true for any odd cycle, so $G_{ij}$ is bipartite.
3. Recolor $G_{ij}$: take a bipartition, and color one half of it color $i$ and the other half color $j$.

This idea is due to Aravind in a comment and in a currently-deleted answer.

After we do the procedure above, color classes $i$ and $j$ are both independent sets in $G_{ij}$; because $G_{ij}$ is an induced subgraph, they are independent sets in $G$. In particular, each of them still includes at most half of the vertices in any cycle. So we still have a half-cycle coloring.

Repeat the procedure to pairs of colors until we've tweaked every color at least once. (When the number of colors is odd, some colors will be considered multiple times, but that's fine.) At the end, each color class is an independent set, so we have a proper coloring with the same number of colors.