Chvátal first learned of graph theory in 1964, on finding a book byClaude Berge in aPlzeň bookstore[8] and much of his research involves graph theory:
His first mathematical publication, at the age of 19, concerneddirected graphs that cannot be mapped to themselves by any nontrivialgraph homomorphism[9]
A 1972 paper[11] relating Hamiltonian cycles to connectivity andmaximum independent set size of a graph, earned Chvátal hisErdős number of 1. Specifically, if there exists ans such that a given graph iss-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 andErdő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,[12] Chvátal introduced the concept ofgraph toughness, a measure ofgraph connectivity that is closely connected to the existence ofHamiltonian cycles. A graph ist-tough if, for everyk greater than 1, the removal of fewer thantk vertices leaves fewer thank 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 equivalentlyhypergraphs, a subject already occurring in his Ph.D. thesis, where he also studiedRamsey 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 takingsubsets, 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.
Chvátal first became interested inlinear programming through the influence ofJack Edmonds while Chvátal was a student at Waterloo.[4] He quickly recognized the importance ofcutting planes for attacking combinatorial optimization problems such as computingmaximum independent sets and, in particular, introduced the notion of a cutting-plane proof.[18][19][20][21] At Stanford in the 1970s, he began writing his popular textbook,Linear Programming, which was published in 1983.[4]
Cutting planes lie at the heart of thebranch and cut method used by efficient solvers for thetraveling salesman problem. Between 1988 and 2005, the team ofDavid L. Applegate,Robert E. Bixby, Vašek Chvátal, andWilliam J. Cook developed one such solver,Concorde.[22][23] The team was awarded The Beale-Orchard-Hays Prize for Excellence in Computational Mathematical Programming[24] in 2000 for their ten-page paper[25] enumerating some of Concorde's refinements of the branch and cut method that led to the solution of a 13,509-city instance and it was awarded theFrederick W. Lanchester Prize in 2007 for their book,The Traveling Salesman Problem: A Computational Study.
