Derrick Stolee - Iowa State University - Research Browser

Color-Blind Index
A graph
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

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


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
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

Derrick Stolee - Iowa State University - Research Browser