Name
Abstract | ||
|---|---|---|
Haramaty and Sudan considered the problem of transmitting a message between two people, Alice and Bob, when Alice's and Bob's priors on the message are allowed to differ by at most a given factor. To find a deterministic compression scheme for this problem, they showed that it is sufficient to obtain an upper bound on the chromatic number of a graph, denoted U(N, s, k) for parameters N, s, k, whose vertices are nested sequences of subsets and whose edges are between vertices that have similar sequences of sets. In turn, there is a close relationship between the problem of determining the chromatic number of U(N, s, k) and a local graph coloring problem considered by Erdos et al. We generalize the results of Erdos et al. by finding bounds on the chromatic numbers of graphs H and G when there is a ho- momorphism phi : H -> G that satisfies a nice property. We then use these results to improve upper and lower bounds on chi(U (N , s, k)). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.37236/6468 | ELECTRONIC JOURNAL OF COMBINATORICS |
DocType | Volume | Issue |
Journal | 25 | 4 |
ISSN | Citations | PageRank |
1077-8926 | 0 | 0.34 |
References | Authors | |
3 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noah Golowich | 1 | 39 | 2.69 |