A Vizing-like theorem for union vertex-distinguishing edge coloring
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2016
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908968070152192 |
|---|---|
| author | Bousquet, Nicolas Dailly, Antoine Duchene, Eric Kheddouci, Hamamache Parreau, Aline |
| author_facet | Bousquet, Nicolas Dailly, Antoine Duchene, Eric Kheddouci, Hamamache Parreau, Aline |
| contents | We introduce a variant of the vertex-distinguishing edge coloring problem, where each edge is assigned a subset of colors. The label of a vertex is the union of the sets of colors on edges incident to it. In this paper we investigate the problem of finding a coloring with the minimum number of colors where every vertex receives a distinct label. Finding such a coloring generalizes several other well-known problems of vertex-distinguishing colorings in graphs.We show that for any graph (without connected component reduced to an edge or a single vertex), the minimum number of colors for which such a coloring exists can only take 3possible values depending on the order of the graph. Moreover, we provide the exact value for paths, cycles and complete binary trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1605_02588 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | A Vizing-like theorem for union vertex-distinguishing edge coloring Bousquet, Nicolas Dailly, Antoine Duchene, Eric Kheddouci, Hamamache Parreau, Aline Discrete Mathematics Combinatorics We introduce a variant of the vertex-distinguishing edge coloring problem, where each edge is assigned a subset of colors. The label of a vertex is the union of the sets of colors on edges incident to it. In this paper we investigate the problem of finding a coloring with the minimum number of colors where every vertex receives a distinct label. Finding such a coloring generalizes several other well-known problems of vertex-distinguishing colorings in graphs.We show that for any graph (without connected component reduced to an edge or a single vertex), the minimum number of colors for which such a coloring exists can only take 3possible values depending on the order of the graph. Moreover, we provide the exact value for paths, cycles and complete binary trees. |
| title | A Vizing-like theorem for union vertex-distinguishing edge coloring |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/1605.02588 |