Color-Blind Index

Problem and Results Summary

Let $c : E(G) \to \{1,\dots,k\}$ be a coloring of the edges of a graph $G$.
For a vertex $v \in V(G)$, let $\overline{c}(v) = (t_1,\dots,t_k)$ where $t_i$ is the number of edges incident to $v$ that have color $i$.
Then, sort the values of $\overline{c}(v)$ to find the *color-blind partition* $c^*(v)$.
We say that a coloring $c$ is *color-blind distinguishing* if $c^*$ is a proper vertex-coloring.
The minimum $k$ such that a color-blind distinguishing $k$-coloring exists is the *color-blind index* of $G$.

Unlike normal vertex or edge colorings, there does not always exist a color-blind distinguishing coloring. All known examples of graphs with no such coloring have minimum degree at most three.

As part of GRWC 2014, we investigated these low-degree graphs. We gain a lot more information about graphs of low degree that have or do not have color-blind distinguishing colorings. We study several classes of graphs, including bipartite regular graphs, 3-regular graphs where every vertex is in at least one 3-cycle, and cacti.

The investigation becomes more complicated as we find that it is NP-complete to distinguish between color-blind index 2 or 3.

Research Papers

J. Diemunsch, N. Graber, L. Kramer, V. Larsen, L.M. Nelsen, L.L. Nelsen, D. Sigler, D. Stolee, C. Suer, Color-blind index in graphs of very low degree.

Web Version ArXiv Version

Web Version ArXiv Version

Software

ColorBlindIndex.sws is a Sage worksheet that contains many helpful routines, including constructing and testing the reducible configurations.

Support

This collaboration began as part of the 2014 Rocky Mountain/Great Plains Graduate Research Workshop in Combinatorics, supported in part by NSF Grant #1427526.

Related Work

R. Kalinowski, M. Pilśniak, J. Przybyło, and M. Woźniak. Can colour-blind distinguish colour palettes?
*The Electronic Journal of Combinatorics*, 20(3):P23, 2013.

Official Version

Official Version

J. Przybyło. On colour-blind distinguishing colour pallets in regular graphs. *Journal of Combinatorial Optimization*, pages 1-10, 2012.
Official Version

J. Przybyło. Colour-blind can distinguish colour pallets. *The Electronic Journal of Combinatorics*, 21(2):P2-19, 2014.
Official Version