Color-blind index in graphs of very low degree
| Autor: | Jennifer Diemunsch, Nathan Graber, Derrick Stolee, Charlie Suer, Victor Larsen, Lauren M. Nelsen, Lucas Kramer, Luke L. Nelsen, Devon Sigler |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
Vertex (graph theory) 021103 operations research Applied Mathematics 0211 other engineering and technologies Color blind 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Combinatorics Edge coloring 05C15 010201 computation theory & mathematics FOS: Mathematics Bipartite graph Discrete Mathematics and Combinatorics Partition (number theory) Mathematics - Combinatorics Bound graph Combinatorics (math.CO) Mathematics |
| Popis: | Let $c:E(G)\to [k]$ be an edge-coloring of a graph $G$, not necessarily proper. For each vertex $v$, let $\bar{c}(v)=(a_1,\ldots,a_k)$, where $a_i$ is the number of edges incident to $v$ with color $i$. Reorder $\bar{c}(v)$ 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)\neq c^*(v)$ for every edge $uv$ 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)\to [k]$ is the color-blind index of $G$, denoted $\operatorname{dal}(G)$. We demonstrate that determining the color-blind index is more subtle than previously thought. In particular, determining if $\operatorname{dal}(G) \leq 2$ is NP-complete. We also connect the color-blind index of a regular bipartite graph to 2-colorable regular hypergraphs and characterize when $\operatorname{dal}(G)$ is finite for a class of 3-regular graphs. 10 pages, 3 figures, and a 4 page appendix |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|