Václav Chvátal

Last updated
Václav Chvátal
Václav Chvátal (2007)
Born (1946-07-20) 20 July 1946 (age 73)
Nationality Canadian, Czech
Alma mater University of Waterloo
Charles University
Awards Beale–Orchard-Hays Prize (2000) [1]
Docteur Honoris Causa, Université de la Méditerranné (2003)
Frederick W. Lanchester Prize (2007) [2]
John von Neumann Theory Prize (2015) [3]
Scientific career
Fields Mathematics, Computer Science, Operations Research
Institutions Concordia University
Doctoral advisor Crispin Nash-Williams
Doctoral students David Avis (Stanford 1977)
Bruce Reed (McGill 1986)

Václav (Vašek) Chvátal (Czech: [ˈvaːtslaf ˈxvaːtal] is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada. He has published extensively on topics in graph theory, combinatorics, and combinatorial optimization.



Chvátal was born in Prague in 1946 and educated in mathematics at Charles University in Prague, where he studied under the supervision of Zdeněk Hedrlín. [4] He fled Czechoslovakia in 1968, three days after the Soviet invasion, [5] and completed his Ph.D. in Mathematics at the University of Waterloo, under the supervision of Crispin St. J. A. Nash-Williams, in the fall of 1970. [4] [6] Subsequently, he took positions at McGill University (1971 and 1978-1986), Stanford University (1972 and 1974-1977), the Université de Montréal (1972-1974 and 1977-1978), and Rutgers University (1986-2004) before returning to Montreal for the Canada Research Chair in Combinatorial Optimization [7] [5] at Concordia (2004-2011) and the Canada Research Chair in Discrete Mathematics (2011-2014) till his retirement.


The Chvatal graph Chvatal graph.svg
The Chvátal graph

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:

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.

Chvátal first became interested in linear programming through the influence of Jack Edmonds while Chvátal was a student at Waterloo. [4] He quickly recognized the importance of cutting planes for attacking combinatorial optimization problems such as computing maximum 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 the branch and cut method used by efficient solvers for the traveling salesman problem. Between 1988 and 2005, the team of David L. Applegate, Robert E. Bixby, Vašek Chvátal, and William J. Cook developed one such solver, Concorde. [22] [23] The team was awarded The Beale-Orchard-Hays Prize for Excellence in Computational Mathematical Programming in 2000 for their ten-page paper [24] 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 the Frederick W. Lanchester Prize in 2007 for their book, The Traveling Salesman Problem: A Computational Study.

Chvátal is also known for proving the art gallery theorem, [25] [26] [27] [28] for researching a self-describing digital sequence, [29] [30] for his work with David Sankoff on the Chvátal–Sankoff constants controlling the behavior of the longest common subsequence problem on random inputs, [31] and for his work with Endre Szemerédi on hard instances for resolution theorem proving. [32]


Related Research Articles

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics, from evolutionary biology to computer science, etc.

Discrete geometry branch of geometry that studies combinatorial properties and constructive methods of discrete geometric objects

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

Perfect graph type of graph (mathematical structure)

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if we have:

In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes nor odd antiholes. It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006.

In combinatorics, the Dinitz theorem is a statement about the extension of arrays to partial Latin squares, proposed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin.

Happy ending problem theorem that every five points in the plane have a subset forming the vertices of a convex quadrilateral

The "happy ending problem" is the following statement:

In mathematics, the Erdős–Burr conjecture was a problem concerning the Ramsey number of sparse graphs. The conjecture is named after Paul Erdős and Stefan Burr, and is one of many conjectures named after Erdős; it states that the Ramsey number of graphs in any sparse family of graphs should grow linearly in the number of vertices of the graph.

Claude Jacques Berge was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory.

Triangle-free graph undirected graph in which no three vertices form a triangle of edges

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

Grötzsch graph

In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch.

Graph toughness

In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t-tough for a given real number t if, for every integer k > 1, G cannot be split into k different connected components by the removal of fewer than tk vertices. For instance, a graph is 1-tough if the number of components formed by removing a set of vertices is always at most as large as the number of removed vertices. The toughness of a graph is the maximum t for which it is t-tough; this is a finite number for all finite graphs except the complete graphs, which by convention have infinite toughness.

Hypohamiltonian graph graph G is said to be hypohamiltonian if G does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

<i>Discrete Mathematics</i> (journal) journal

Discrete Mathematics is a biweekly peer-reviewed scientific journal in the broad area of discrete mathematics, combinatorics, graph theory, and their applications. It was established in 1971 and is published by North-Holland Publishing Company. It publishes both short notes, full length contributions, as well as survey articles. In addition, the journal publishes a number of special issues each year dedicated to a particular topic. Although originally it published articles in French and German, it now allows only English language articles. The editor-in-chief is Douglas West.

Chvátal graph a triangle-free 4-regular 4-chromatic graph with 12 vertices and 24 edges

In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal (1970).

John Adrian Bondy, a dual British and Canadian citizen, was a professor of graph theory at the University of Waterloo, in Canada. He is a faculty member of Université Lyon 1, France. Bondy is known for his work on Bondy–Chvátal theorem together with Václav Chvátal. His coauthors include Paul Erdős.

Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.

Paul Allen Catlin was a mathematician, professor of mathematics and Doctor of Mathematics, known for his valuable contributions to graph theory and number theory. He wrote one of the most cited papers in the series of chromatic numbers and Brooks' theorem, titled Hajós graph coloring conjecture: variations and counterexamples.

William J. Cook American mathematician

William John Cook is an American operations researcher and mathematician, and Professor of Applied Mathematics and Statistics at Johns Hopkins University, where he joined the faculty in 2018. He is a member of the National Academy of Engineering. He is known for his work on the traveling salesman problem and is one of the authors of the Concorde TSP Solver.

Fleischners theorem

In graph theory, a branch of mathematics, Fleischner's theorem gives a sufficient condition for a graph to contain a Hamiltonian cycle. It states that, if G is a 2-vertex-connected graph, then the square of G is Hamiltonian. it is named after Herbert Fleischner, who published its proof in 1974.


  1. Past Winners of The Beale-Orchard-Hays Prize.
  2. Frederick W. Lanchester Prize 2007, retrieved 2017-03-19.
  3. John von Neumann Theory Prize 2015, retrieved 2017-03-19.
  4. 1 2 3 4 5 6 Avis, D.; Bondy, A.; Cook, W.; Reed, B. (2007). "Vasek Chvatal: A Short Introduction" (PDF). Graphs and Combinatorics . 23: 41–66. CiteSeerX . doi:10.1007/s00373-007-0721-4.
  5. 1 2 Vasek Chvátal is ‘the travelling professor’, Concordia's Thursday Report, Feb. 10, 2005.
  6. The Mathematics Genealogy Project – Václav Chvátal
  7. Vasek Chvatal awarded Canada Research Chair, Concordia's Thursday Report, Oct. 23, 2003.
  8. Chvátal, Vašek (1997), "In praise of Claude Berge", Discrete Mathematics , 165-166: 3–9, doi:10.1016/s0012-365x(96)00156-2 ,
  9. Chvátal, Václav (1965), "On finite and countable rigid graphs and tournaments", Commentationes Mathematicae Universitatis Carolinae , 6: 429–438.
  10. Weisstein, Eric W. "Chvátal Graph". MathWorld .
  11. V. Chvátal; P. Erdős (1972), "A note on Hamiltonian circuits" (PDF), Discrete Mathematics , 2 (2): 111–113, doi:10.1016/0012-365x(72)90079-9 ,
  12. Chvátal, V. (1973), "Tough graphs and hamiltonian circuits", Discrete Mathematics , 5 (3): 215–228, doi:10.1016/0012-365x(73)90138-6 ,
  13. Lesniak, Linda, Chvátal's t0-tough conjecture (PDF)
  14. Mathematical Reviews MR0369170
  15. V. Chvátal; David A. Klarner; D.E. Knuth (1972), "Selected combinatorial research problems" (PDF), Computer Science Department, Stanford University, Stan-CS-TR-72-292: Problem 25
  16. Chvátal, Vašek, A conjecture in extremal combinatorics
  17. "A greedy heuristic for the set-covering problem", Mathematics of Operations Research, 1979
  18. Chvátal, Václav (1973), "Edmonds polytopes and weakly hamiltonian graphs", Mathematical Programming, 5: 29–40, doi:10.1007/BF01580109 ,
  19. Chvátal, Václav (1973), "Edmonds polytopes and a hierarchy of combinatorial problems", Discrete Mathematics, 4 (4): 305–337, doi:10.1016/0012-365x(73)90167-2 ,
  20. Chvátal, Václav (1975), "Some linear programming aspects of combinatorics" (PDF), Congressus Numerantium, 13: 2–30,
  21. Chvátal, V. (1975), "On certain polytopes associated with graphs", Journal of Combinatorial Theory, Series B, 18 (2): 138–154, doi:10.1016/0095-8956(75)90041-6 .
  22. Math Problem, Long Baffling, Slowly Yields. New York Times, Mar. 12, 1991.
  23. Artful Routes, Science News Online, Jan. 1, 2005.
  24. Applegate, David; Bixby, Robert; Chvátal, Vašek; Cook, William (1998), "On the Solution of Traveling Salesman Problems", Documenta Mathematica, Extra Volume ICM III
  25. Weisstein, Eric W. "Art Gallery Theorem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ArtGalleryTheorem.html
  26. Diagonals: Part I 4. Art gallery problems, AMS Feature Column by Joseph Malkevitch
  27. Chvatal's Art Gallery Theorem in Alexander Bogomolny's Cut the Knot
  28. Obsession, Numb3rs, Episode 3, Season 2
  29. Chvátal, Vašek (1993), "Notes on the Kolakoski Sequence", DIMACS Technical Reports, TR: 93-84
  30. Dangerous Problems, Science News Online, Jul. 13, 2002.
  31. Chvátal, Václav; Sankoff, David (1975), "Longest common subsequences of two random sequences", Journal of Applied Probability, 12 (2): 306–315, doi:10.2307/3212444, JSTOR   3212444 .
  32. Chvátal, Vašek; Szemerédi, Endre (1988), "Many hard examples for resolution", Journal of the ACM, 35 (4): 759–768, doi:10.1145/48014.48016 .