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!
|
| _version_ | 1849344711769194496 |
|---|---|
| author | Sebastian Czerwiński |
| author_facet | Sebastian Czerwiński |
| author_sort | Sebastian Czerwiński |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-1a097b8d59d94f859dd8f43dc5c6d351 |
| institution | Kabale University |
| issn | 1365-8050 |
| language | English |
| publishDate | 2024-07-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-1a097b8d59d94f859dd8f43dc5c6d3512025-08-20T03:42:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502024-07-01vol. 26:2Graph Theory10.46298/dmtcs.1110111101On harmonious coloring of hypergraphsSebastian CzerwińskiA 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.http://dmtcs.episciences.org/11101/pdfmathematics - combinatorics05c15 |
| spellingShingle | Sebastian Czerwiński On harmonious coloring of hypergraphs Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics 05c15 |
| title | On harmonious coloring of hypergraphs |
| title_full | On harmonious coloring of hypergraphs |
| title_fullStr | On harmonious coloring of hypergraphs |
| title_full_unstemmed | On harmonious coloring of hypergraphs |
| title_short | On harmonious coloring of hypergraphs |
| title_sort | on harmonious coloring of hypergraphs |
| topic | mathematics - combinatorics 05c15 |
| url | http://dmtcs.episciences.org/11101/pdf |
| work_keys_str_mv | AT sebastianczerwinski onharmoniouscoloringofhypergraphs |