Color-blind index in graphs of very low degree

Abstract: Let

c : E (G) o [k]

be an edge-coloring of a graph

G

, not necessarily proper. For each vertex

v

, let

, where

a_{i}

is the number of edges incident to

v

with color

i

. Reorder

for every

v

in

G

in nonincreasing order to obtain

c^{*} (v)

, the color-blind partition of

v

. When

c^{*}

induces a proper vertex coloring, that is,

c^{*} (u) e q c^{*} (v)

for every edge

u v

in

G

, we say that

c

is color-blind distinguishing. The minimum

k

for which there exists a color-blind distinguishing edge coloring

c : E (G) o [k]

is the color-blind index of

G

, denoted

o p e r a t o r n a m e d a l (G)

. We demonstrate that determining the color-blind index is more subtle than previously thought. In particular, determining if

o p e r a t o r n a m e d a l (G) l e q 2

is NP-complete. We also connect the color-blind index of a regular bipartite graph to 2-colorable regular hypergraphs and characterize when

o p e r a t o r n a m e d a l (G)

is finite for a class of 3-regular graphs.

Recommendations

Cites Work

This page was built for publication: Color-blind index in graphs of very low degree