On harmonious coloring of hypergraphs
A harmonious coloring of a $k$-uniform hypergraph $H$ is a vertex coloring such that no two vertices in the same edge have the same color, and each $k$-element subset of colors appears on at most one edge. The harmonious number $h(H)$ is the least number of colors needed for such a coloring. The p...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2024-07-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/11101/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | A harmonious coloring of a $k$-uniform hypergraph $H$ is a vertex coloring such that no two vertices in the same edge have the same color, and each $k$-element subset of colors appears on at most one edge. The harmonious number $h(H)$ is the least number of colors needed for such a coloring. The paper contains a new proof of the upper bound $h(H)=O(\sqrt[k]{k!m})$ on the harmonious number of hypergraphs of maximum degree $\Delta$ with $m$ edges. We use the local cut lemma of A. Bernshteyn. |
|---|---|
| ISSN: | 1365-8050 |