Václav Chvátal

Václav (Vašek) Chvátal (Czech:

Chvátal first learned of graph theory in 1964, on finding a book by Claude Berge in a Pilsen bookstore ^[8] and much of his research involves graph theory:

• His first mathematical publication, at the age of 19, concerned directed graphs that cannot be mapped to themselves by any nontrivial graph homomorphism^[9]
• Another graph-theoretic result of Chvátal was the 1970 construction of the smallest possible
  chromatic and 4-regular, now known as the Chvátal graph.^[4][10]
• A 1972 paper
  maximum independent set size of a graph, earned Chvátal his Erdős number of 1. Specifically, if there exists an s such that a given graph is s-vertex-connected and has no (s + 1)-vertex independent set, the graph must be Hamiltonian. Avis et al.^[4] tell the story of Chvátal and Erdős
  working out this result over the course of a long road trip, and later thanking Louise Guy "for her steady driving."
• In a 1973 paper,
  Hamiltonian cycles. A graph is t-tough if, for every k greater than 1, the removal of fewer than tk vertices leaves fewer than k connected components in the remaining subgraph. For instance, in a graph with a Hamiltonian cycle, the removal of any nonempty set of vertices partitions the cycle into at most as many pieces as the number of removed vertices, so Hamiltonian graphs are 1-tough. Chvátal conjectured that 3/2-tough graphs, and later that 2-tough graphs, are always Hamiltonian; despite later researchers finding counterexamples to these conjectures, it still remains open whether some constant bound on the graph toughness is enough to guarantee Hamiltonicity.^[13]

Some of Chvátal's work concerns families of sets, or equivalently hypergraphs, a subject already occurring in his Ph.D. thesis, where he also studied Ramsey theory.

• In a 1972 conjecture that Erdős called "surprising" and "beautiful",^[14] and that remains open (with a $10 prize offered by Chvátal for its solution) ^[15][16] he suggested that, in any family of sets closed under the operation of taking subsets, the largest pairwise-intersecting subfamily may always be found by choosing an element of one of the sets and keeping all sets containing that element.
• In 1979,^[17] he studied a weighted version of the set cover problem, and proved that a greedy algorithm provides good approximations to the optimal solution, generalizing previous unweighted results by David S. Johnson (J. Comp. Sys. Sci. 1974) and László Lovász (Discrete Math. 1975).

Chvátal first became interested in

• Vašek Chvátal (1983). Linear Programming. W.H. Freeman.
  ISBN 978-0-7167-1587-0
  .. Japanese translation published by Keigaku Shuppan, Tokyo, 1986.
• ISBN 978-0-444-86587-8. {{cite book}}: |author= has generic name (help
  )
• David L. Applegate; Robert E. Bixby; Vašek Chvátal;
  ISBN 978-0-691-12993-8.^[33]
• Vašek Chvátal, ed. (2011). Combinatorial Optimization: Methods and Applications. IOS Press.
  ISBN 978-1-60750-717-8
  .
• Vašek Chvátal (2021). Discrete Mathematical Charms of Paul Erdős. A Simple Introduction. Cambridge University Press.
  ISBN 978-1-108-92740-6
  .

• List of University of Waterloo people

References