Pavol Hell
Jump to navigation
Jump to search
Pavol Hell was a person.
- Context:
- He has Erdős Number of 1.
- See: Computational Graph Theory.
References
- Professional Home Page: http://www.cs.sfu.ca/~pavol/
- Google Scholar Author Page: http://scholar.google.com/citations?user=8KDwlbEAAAAJ
1999
- (Feder et al., 1999) ⇒ Tomas Feder, Pavol Hell, Sulamita Klein, and Rajeev Motwani. (1999). “Complexity of Graph Partition Problems.” In: Proceedings of the thirty-first annual ACM symposium on Theory of computing, pp. 464-472. ACM, 1999.
1990
- (Hell & Nešetřil, 1990) ⇒ Pavol Hell, and Jaroslav Nešetřil. (1990). “On the complexity of h-coloring.” In: Journal of Combinatorial Theory, 48(1).
1989
- (Erdös et al., 1989) ⇒ Paul Erdős, Pavol Hell and Peter Winkler. (1989). “Bandwidth Versus Bandsize.” In: Annals of Discrete Math. doi:10.1016/S0167-5060(08)70455-2
- QUOTE: The bandwidth (bandsize) of a graph G is the minimum, over all bijections u: V(G) → {1,2,…,|V(G)|}, of the greatest difference (respectively the number of distinct differences) |u(v) — u(w)| for vw ɛE(G).
We show that a graph on n vertices with bandsize k has bandwidth between k and cn1-1/n, and that this is best possible. In the process we obtain best possible asymptotic bounds on the bandwidth of circulant graphs.
The bandwidth and bandsize of random graphs are also compared, the former turning out to be n — C1 log n and the latter at least n — c2 (logn)2.
- QUOTE: The bandwidth (bandsize) of a graph G is the minimum, over all bijections u: V(G) → {1,2,…,|V(G)|}, of the greatest difference (respectively the number of distinct differences) |u(v) — u(w)| for vw ɛE(G).