TITLE
WHICH PERFECT GRAPHS DO WE KNOW?

BY
Vasek Chvátal
Rutgers University

ABSTRACT

In 1960, Claude Berge introduced the notion of a perfect graph and proposed his famous Strong Perfect Graph Conjecture. Forty years later, the conjecture remains open and perfect graphs have become one of the focal points of graph theory: the bibliography on the subject at
http://www.cs.rutgers.edu/~chvatal/perfect/papers.html
has well over 500 items. I will talk about the problem of recognizing perfect graphs in polynomial time.

BIOGRAPHY

PERSONAL DATA Vasek Chvátal. Born July 20, 1946, in Prague. Canadian citizen since 1974;U.S. permanent resident since 1992.
M.A. equivalent (Mathematics), Charles University, 1968;Ph.D. (Mathematics), University of Waterloo, 1970.
POSITIONS HELD: 1986-present: Professor II, Computer Science, Rutgers University1989-1990: John von Neumann Professor, Forschungsinstitut f. Diskrete Matematik,
Universit"at Bonn (on leave from Rutgers)1988-1989: A.v.Humboldt Distinguished Senior Scientist, Forschungsinstitut f. Diskrete Matematik, Universit"at Bonn (on leave from Rutgers)1982-1986: Professor, Computer Science, McGill University 1978-1982: Associate Professor, Computer Science, McGill University1977-1978: Associate Professor, Computer Science and Operations Research, Stanford University
(on leave to Universit'e de Montr'eal)1974-1977: Assistant Professor, Computer Science and Operations Research, Stanford University 1972-1974: Membre visiteur, Centre de recherches math'ematiques, Universit'e de Montr'eal1972: Visiting Assistant Professor, Stanford University 1971: Visiting Assistant Professor, McGill University1970-1971: N.R.C. Postdoctoral Fellow, University of Waterloo
ASSOCIATE EDITOR OF: Discrete Applied Mathematics (1979-present)Discrete Mathematics (1979-present)
Journal of Combinatorial Theory B (1983-1986)Mathematical Programming (1972-1982) SIAM Journal on Algebraic and Discrete Methods (1979-1986)
PROFESSIONAL ACTIVITIES:
* Member of the N.R.C. Grant selection committee in Pure and Applied Mathematics(1977-1980; Chairman, 1979-1980)
* Member of Council, Canadian Mathematical Society (1979-1981)
* Member of the International Program Committe,13th International Symposium on Mathematical Programming (Tokyo 1988)
* Member of the International Program Committe,14th International Symposium on Mathematical Programming (Amsterdam 1991)

Fall 2000 Colloquia Page || EECS Main Page