Article · Wikipedia archive · Last revised Jun 17, 2026

Raphael Yuster

Raphael "Raphy" Yuster is an Israeli mathematician specializing in combinatorics and graph theory. He is a professor of mathematics at the University of Haifa. He is a recipient of the Nerode Prize for his work on color-coding,[A] and is also known for the Alon–Yuster conjecture relating the chromatic numbers of graphs to the number of disjoint copies of a smaller graph that can be found in a larger one, later proven by János Komlós, Gábor N. Sárközy, and Endre Szemerédi.[B]

Last revised
Jun 17, 2026
Read time
≈ 2 min
Length
347 w
Citations
7
Source
Wikipedia ↗

Raphael "Raphy" Yuster (Hebrew: רפאל יוסטר) is an Israeli mathematician specializing in combinatorics and graph theory. He is a professor of mathematics at the University of Haifa. He is a recipient of the Nerode Prize for his work on color-coding,1[A] and is also known for the Alon–Yuster conjecture relating the chromatic numbers of graphs to the number of disjoint copies of a smaller graph that can be found in a larger one, later proven by János Komlós, Gábor N. Sárközy, and Endre Szemerédi.2[B]

Education and career

Yuster was a student at Tel Aviv University, where he received a bachelor's degree in 1989, a master's degree in 1991, and a Ph.D. in 1995.3 His doctoral dissertation, Non Constructive Graph Theoretic Proofs and Their Algorithmic Aspects, was supervised by Noga Alon.4

He has been a faculty member at the University of Haifa since 2004.5

Recognition

With Noga Alon and Uri Zwick, Yuster was a recipient of the 2019 Nerode Prize, given for their work on color coding, an application of the probabilistic method to subgraph isomorphism.1[A]

His work with Zwick on sparse matrix multiplication received the 2023 European Symposium on Algorithms Test-of-Time Award.6[C]

Selected publications

A.
Alon, Noga; Yuster, Raphael; Zwick, Uri (1995), "Color-coding", Journal of the ACM, 42 (4): 844–856, doi:10.1145/210332.210337, MR 1411787
B.
Alon, Noga; Yuster, Raphael (1996), "H-factors in dense graphs", Journal of Combinatorial Theory, Series B, 66 (2): 269–282, doi:10.1006/jctb.1996.0020, MR 1376050
C.
Yuster, Raphael; Zwick, Uri (2005), "Fast sparse matrix multiplication", ACM Transactions on Algorithms, 1 (1): 2–13, doi:10.1145/1077464.1077466, MR 2163127; previously announced at ESA 2004
See also

See also

References

References

  1. EATCS-IPEC Nerode Prize 2019, European Association for Theoretical Computer Science, retrieved 2025-04-11
  2. Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre (2001), "Proof of the Alon–Yuster conjecture", Discrete Mathematics, 235 (1–3): 255–269, doi:10.1016/S0012-365X(00)00279-X, MR 1829855
  3. Yuster, Raphael, Education, University of Haifa, retrieved 2025-04-11
  4. Raphael Yuster at the Mathematics Genealogy Project
  5. "Raphael Yuster", ORCiD, retrieved 2025-04-11
  6. "ESA Test-of-Time Award 2023", European Symposium on Algorithms, retrieved 2025-04-11
External links