Name
Abstract | ||
|---|---|---|
Given an r-uniform hypergraph H = (V, E) and a weight function omega : E -> {1, ..., w}, a coloring of vertices of H, induced by w, is defined by c(v) = Sigma(e is an element of v) w(e) for all v is an element of V. If there exists such a coloring that is strong (that means in each edge no color appears more than once), then we say that H is strongly w-weighted. Similarly, if the coloring is weak (that means there is no monochromatic edge), then we say that H is weakly w-weighted. In this paper, we show that almost all 3 or 4-uniform hypergraphs are strongly 2-weighted (but not 1-weighted) and almost all 5-uniform hypergraphs are either 1 or 2 strongly weighted (with a nontrivial distribution). Furthermore, for r >= 6 we show that almost all r-uniform hypergraphs are strongly 1-weighted. We complement these results by showing that almost all 3-uniform hypergraphs are weakly 2-weighted but not 1-weighted and for r >= 4 almost all r uniform hypergraphs are weakly 1-weighted. These results extend a previous work of Addario-Berry, Dalal and Reed for graphs. We also prove general lower bounds and show that there are r-uniform hypergraphs which are not strongly (r(2) - r)- weighted and not weakly 2-weighted. Finally, we show that determining whether a particular uniform hypergraph is strongly 2-weighted is NP-complete. |
Year | Venue | Field |
|---|---|---|
2016 | ELECTRONIC JOURNAL OF COMBINATORICS | Discrete mathematics,Graph,Monochromatic color,Combinatorics,Weight function,Vertex (geometry),Constraint graph,Hypergraph,Omega,Conjecture,Mathematics |
DocType | Volume | Issue |
Journal | 23.0 | 2.0 |
ISSN | Citations | PageRank |
1077-8926 | 4 | 0.42 |
References | Authors | |
4 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| P BENNETT | 1 | 15 | 5.42 |
| Andrzej Dudek | 2 | 114 | 23.10 |
| Alan M. Frieze | 3 | 4837 | 787.00 |
| Laars Helenius | 4 | 6 | 1.15 |