Vašek Chvátal's list of publications

Papers

1. On finite and countable rigid graphs and tournaments, Comment.Math.Univ.Carolin. 6 (1965), 429-438.
2. Remark on a paper of Lovász, Comment.Math.Univ.Carolin. 9 (1968), 47-50.
3. On finite polarized partition relations, Canad.Math.Bull. 12 (1969), 321-326.
4. Planarity of graphs with given degrees of vertices, Nieuw Arch.Wisk. 17 (1969), 47-60.
5. A remark on a problem of Harary, Czechoslovak Math.J. 20 (1970), 109-111.
6. The smallest triangle-free 4-chromatic 4-regular graph, J.Combin.Theory 9 (1970), 93-94.
   • an entry in MathWorld
7. A note on coefficients of chromatic polynomials, J.Combin.Theory 9 (1970), 95-96.
8. Some unknown van der Waerden numbers , in: Combinatorial Structures and Their Applications (R.Guy et al.,eds.), Gordon and Breach, New York, 1970, pp.31-33.
   • citations from Google Scholar
   • Some New Van der Waerden Numbers and Some Van der Waerden-type Numbers by Tanbir Ahmed, INTEGERS: The Electronic Journal of Combinatorial Number Theory 9 (2009).
9. On a problem of Erdős, in: Combinatorial Structures and Their Applications (R.Guy et al.,eds.), Gordon and Breach, New York, 1970, pp.495-497.
10. A remark on Newman's conjecture, in: Proceedings of the Washington State University Conference on Number Theory (J.H.Jordan and W.A.Webb, eds.), Washington State University, 1971, pp.113-129.
11. Hypergraphs and Ramseyian theorems, Proc.Amer.Math.Soc. 27 (1971), 434-440.
12. On finite delta-systems of Erdős and Rado, Acta Math.Acad.Sci.Hungar. 21 (1970), 341-355.
13. Some combinatorial theorems on monotonicity (joint with J. Komlós), Canad.Math.Bull. 14 (1971), 151-157.
    • citations from Google Scholar
14. Some relations among invariants of graphs, Czechoslovak Math.J. 21 (1971), 366-368.
15. Every finite graph is a full subgraph of a rigid graph (joint with P. Hell, L.Kucera and J.Nešetril), J.Combin.Theory (1971), 284-286.
16. A note on hamiltonian circuits (joint with P.Erdős), Discrete Math. 2 (1972), 111-113.
    • citations from Google Scholar
17. Remarks on a problem of Moser, Canad.Math.Bull. 15 (1972), 19-21.
18. On Hamilton's ideals, J.Combin.Theory 12 (1972), 163-168.
    • an entry in MathWorld
    • citations from Google Scholar
19. Flip-flops in hypohamiltonian graphs, Canad.Math.Bull. 16 (1973), 33-42.
20. Generalized Ramsey theory for graphs (joint with F.Harary), Bull.Amer.Math.Soc. 78 (1972), 423-426.
21. Generalized Ramsey theory for graphs II. Small diagonal numbers. (joint with F.Harary), Proc.Amer.Math.Soc. 32 (1972), 389-394.
22. Generalized Ramsey theory for graphs. III. Small off-diagonal numbers. (joint with F.Harary), Pacific J.Math. 41 (1972), 335-345.
23. Ramsey's theorem and self-complementary graphs (joint with P. Erdős and Z.Hedrlín), Discrete Math. 3 (1972), 301-304.
24. Monochromatic paths in edge-colored graphs, J.Combin.Theory 13 (1972), 69-70.
25. Generalized Ramsey theory for graphs. I. Diagonal numbers (joint with F.Harary), Period.Math.Hungar. 3 (1973), 115-124.
26. Tough graphs and hamiltonian circuits, Discrete Math. 5 (1973), 215-228.
    Reprinted in 35th Special Anniversary Issue of Discrete Mathematics (Volume 306, Issues 10-11 , 28 May 2006), 910-917.
    • citations from Google Scholar
    • Problem 21 in Stephen Locke's dynamic update of 50 problems
      from J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Elsevier North-Holland 1976.
    • Not every 2-tough graph is Hamiltonian,
      an abstract of a paper by D. Bauer, H.J. Broersma and H.J. Veldman
    • Selected papers by Douglas Bauer
27. Chromatic automorphisms of graphs (joint with J.Sichler), J.Combin. Theory 14 (1973), 209-215.
28. Edmonds polytopes and weakly hamiltonian graphs, Math.Programming 5 (1973), 29-40.
    • citations from Google Scholar
29. Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math. 4 (1973), 305-337.
    Reprinted in 35th Special Anniversary Issue of Discrete Mathematics (Volume 306, Issues 10-11 , 28 May 2006), 886-904.
    • citations from Google Scholar
    • two entries in the INFORMS Mathematical Programming Glossary
    • lecture notes by Catherine H. Gebotys
30. New directions in hamiltonian graph theory, in: New Directions in the Theory of Graphs (F.Harary, ed.), Academic Press, New York, 1973, pp.65-95.
31. Intersecting families of edges in hypergraphs having the hereditary property, in: Hypergraph Seminar (C.Berge et al., eds.), Springer-Verlag, Berlin and New York, 1974, pp.61-66.
    • The conjecture and its bibliography
32. Every digraph has a semi-kernel (joint with L.Lovász), in: Hypergraph Seminar (C.Berge et al., eds.), Springer-Verlag, Berlin and New York, 1974, p.17.
33. The minimality of the Mycielski graph, in: Graphs and Combinatorics (R.A.Bari and F.Harary, eds.), Springer-Verlag, Berlin and New York, 1974, pp.243-246.
34. On the Ramsey number of the five-spoked wheel (joint with A.Schwenk), in: Graphs and Combinatorics (R.A.Bari and F.Harary, eds.), Springer-Verlag, Berlin and New York, 1974, pp.247-261.
35. Some linear programming aspects of combinatorics, Congr.Numer. 13 (1975), 2-30.
    • Technical Report STAN-CS-75-05, September 1975
36. On a conjecture of Fejés Tóth, Period.Math.Hungar. 6 (1975), 357-362.
37. An extremal set-intersection theorem, J.London Math.Soc. (1974), 355-359.
    • citations from Google Scholar
38. Longest common subsequences of two random sequences (joint with D. Sankoff), J.Appl.Probab. (1975), 306-315.
    • citations from Google Scholar
    • Marcos Kiwi and José Soto, On a speculated relation between Chvátal-Sankoff constants of several sequences, arXiv:0810.1066v1 [math.CO]
39. A combinatorial theorem in plane geometry, J.Combin.Theory 18 (1975), 39-41.
    • citations from Google Scholar
    • an entry in MathWorld
    • AMS Feature Column by Joseph Malkevitch
    • A column in Alexander Bogomolny's Interactive Mathematics Miscellany and Puzzles
    • "Obsession": Episode 16, Season 2 of the TV series Numb3rs.
40. On certain polytopes associated with graphs, J.Combin.Theory 18 (1975), 138-154.
    • citations from Google Scholar
41. D.Ray Fulkerson's contributions to Operations Research, Math.Oper.Res. 1 (1976), 311-320.
42. Degrees and matchings (joint with D.Hanson), J.Combin.Theory 20 (1976), 128-138.
43. On the strong perfect graph conjecture, J.Combin.Theory 20 (1976), 139-141.
44. A method in graph theory (joint with J.A.Bondy), Discrete Math. 15 (1976), 111-135.
    • citations from Google Scholar
    • lecture notes by Stephen Locke
    • an entry in MathWorld
    • Bondy and Chvátal's theorem from PlanetMath.org
45. There are $2^{\aleph_{\alpha}}$ friendship graphs of cardinal $\aleph_{\alpha}$ (joint with R.O.Davies, A.Kotzig, and I.G.Rosenberg), Canad.Math.Bull. 19 (1976), 431-433.
46. Tree-complete graph Ramsey numbers, J.Graph Theory 1 (1977), 93.
    • citations from Google Scholar
47. Aggregation of inequalities in integer programming (joint with P.L. Hammer), Ann.Discrete Math. 1 (1977), 145-162.
    • citations from Google Scholar
48. Determining the stability number of a graph, SIAM J.Comput. 6 (1977), 643-662.
    • citations from Google Scholar
49. Distances in orientations of graphs (joint with C.Thomassen), J. Combin.Theory Ser.B 24 (1978), 61-75.
    • citations from Google Scholar
50. Biased positional games (joint with P.Erdős), Ann.Discrete Math. 2 (1978), 221-229.
    • citations from Google Scholar
51. Two results concerning multicoloring (joint with M.Garey and D.S.Johnson), Ann.Discrete Math. 2 (1978), 151-154.
52. Notes on Bland's pivoting rule (joint with D.Avis), Math.Programming Study 8 (1978), 24-34.
    • citations from Google Scholar
53. The tail of the hypergeometric distribution, Discrete Math. 25 (1979), 285-287.
    • citations from Google Scholar
54. Combinatorial designs related to the strong perfect graph conjecture (joint with R.L.Graham, A.F.Perold and S.H.Whitesides), Discrete Math. 26 (1979), 83-92.
55. A greedy heuristic for the set-covering problem, Math.Oper.Res. 4 (1979), 233-235.
    • citations from Google Scholar
56. Three-regular subgraphs of four-regular graphs (joint with H. Fleischner, J.Sheehan and C.Thomassen), J.Graph Theory 3 (1979), 371-386.
57. Tricky problems, simple algorithms, in: 1979 International Symposium on Circuits and Systems Proceedings, The IEEE Circuits and Systems Society, 1979, pp.254-255.
58. Recognizing intersection patterns, Ann.Discrete Math. 8 (1980), 249-251.
59. Hard knapsack problems, Oper.Res. 28 (1980), 1402-1411.
    • Notes on Cryptography by Charles Blair
60. Finding largest convex subsets (joint with G.Klincsek), Congr. Numer. 29 (1980), 453-460.
61. On the Erdős-Stone theorem (joint with E.Szemerédi), J. London Math.Soc. (2) 23 (1981), 207-214.
62. A short proof of the linear arboricity for cubic graphs (joint with J.Akiyama), Bull. Liber. Arts & Sci., NMS No.2 (1981), (1)-(3).
63. Balancing signed graphs (joint with J.Akiyama, D.Avis and H.Era), Discrete Appl.Math. 3 (1981), 227-233.
64. Combinatorial properties of polyominoes (joint with C.Berge, C.C. Chen and C.S.Seow), Combinatorica 1 (1981), 217-224.
65. Cheap, middling, or dear, in: The Mathematical Gardner (D.A.Klarner, ed.), Prindle,Weber\&Schmidt, Boston, 1981, pp.44-50.
66. Crossing-free subgraphs (joint with M.Ajtai, M.M.Newborn and E. Szemerédi), Ann.Discrete Math. 12 (1982), 9-12.
    • citations from Google Scholar
    • An entry in Wikipedia
67. On the bicycle problem, Discrete Appl.Math. 5 (1983), 165-173.
68. On an extremal problem concerning intervals (joint with E. Szemerédi), European J.Combin. 3 (1982), 215-217.
69. Notes on the Erdős-Stone theorem (joint with E.Szemerédi), Ann.Discrete Math. 17 (1983), 183-190.
70. The Ramsey number of a graph with a bounded maximum degree (joint with V.Rödl, E.Szemerédi, and W.T.Trotter, Jr.), J. Combinatorial Theory Ser.B 34 (1983), 239-243.
71. Short cycles in directed graphs (joint with E.Szemerédi), J. Combinatorial Theory Ser.B 35 (1983), 323-327.
    • citations from Google Scholar
72. Mastermind, Combinatorica 3 (1983), 325-329.
    • an entry in MathWorld
    • Michael T. Goodrich, On the algorithmic complexity of the Mastermind game with black-peg results, arXiv:0904.4911v1 [cs.DS]
73. A Semi-Strong Perfect Graph Conjecture, Ann.Discrete Math. 21 (1984), 279-280.
74. Perfectly ordered graphs, Ann.Discrete Math. 21 (1984), 63-65.
75. Notes on perfect graphs, in: Progress in Combinatorial Optimization (W.R.Pulleyblank, ed.), Academic Press, 1984, pp.107-115.
76. Recognizing decomposable graphs, J.Graph Theory 8 (1984), 51-3.
77. Probabilistic methods in graph theory, Ann.Oper.Res. 1 (1984), 171-182.
78. Recent results on perfect graphs, in: 1985 International Symposium on Circuits and Systems Proceedings, The IEEE Circuits and Systems Society, 1985, pp.1183-1186.
79. Cutting planes in combinatorics, European J.Combin. 6 (1985), 217-226.
80. Hamiltonian cycles, in: The Traveling Salesman Problem (E.L.Lawler et al., eds.), John Wiley, 1985, pp.403-429.
81. Star-cutsets and perfect graphs, J.Combinatorial Theory Ser.B 39 (1985), 189-199.
    • citations from Google Scholar
82. On the P₄-structure of perfect graphs I. Even decompositions (joint with C.T.Hoàng), J.Combinatorial Theory Ser.B 39 (1985), 209-219.
83. Bull-free Berge graphs are perfect (joint with N.Sbihi), Graphs Combin. 3 (1987), 127-139.
84. Perfect graphs, in: Surveys in Combinatorics 1987 (C.Whitehead, ed.), LMS Lecture Notes 123, Cambridge University Press, 1987, pp.43-51.
85. On the maximum weight clique problem (joint with E.Balas and J. Nešetril), Math.Oper.Res. 12 (1987), 522-535.
86. Four classes of perfectly orderable graphs (joint with C.T.Hoàng, N.V.R.Mahadev, and D.deWerra), J.Graph Theory 11 (1987), 481-495.
87. On the P₄-structure of perfect graphs III. Partner decompositions, J.Combinatorial Theory Ser.B 43 (1987), 349-353.
88. Recognizing claw-free perfect graphs (joint with N.Sbihi), J. Combinatorial Theory Ser.B 44 (1988), 154-176.
    • F.Maffray and B.A. Reed, A description of claw-free perfect graphs, J. Combinatorial Theory Ser.B 75 (1999), 134-156.
89. Many hard examples for resolution (joint with E.Szemerédi), J.Assoc.Comput.Mach. 35 (1988), 759-768.
    • citations from Google Scholar
90. On cutting-plane proofs in combinatorial optimization (joint with W. Cook and M.Hartmann), Linear Algebra Appl. 114/115 (1989), 455-499.
    • citations from Google Scholar
91. A note on the traveling salesman problem, Oper.Res.Lett. 8 (1989), 77-78.
92. Two-colorings that decompose perfect graphs (joint with W.J.Lenhart and N.Sbihi), J.Combinatorial Theory Ser.B 49 (1990), 1-9.
93. Which line-graphs are perfectly orderable?, J.Graph Theory 14 (1990), 247-255.
94. Packing paths perfectly (joint with J.Akiyama), Discrete Math. 85 (1990), 247-255.
95. A note on line digraphs and the directed max-cut problem (joint with C.Ebenegger), Discrete Appl.Math. 29 (1990), 165-170.
96. The discipline number of a graph (joint with W.Cook), Discrete Math. 86 (1990), 191-198.
97. Almost all graphs with 1.44n edges are 3-colorable, Random Structures Algorithms 2 (1991) 11-28.
98. Small transversals in hypergraphs (joint with C.McDiarmid), Combinatorica 12 (1992), 19-26.
    • citations from Google Scholar
99. Mick gets some (the odds are on his side) (joint with B.Reed), in: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Washington, 1992, pp. 620--627. A related web page: ...
    • citations from Google Scholar
100. A note on well-covered graphs (joint with P.J.Slater), in: Quo Vadis, Graph Theory? (J.Gimbel et al., eds.), Ann.Discrete Math. 55 (1993), 179-182.
101. Which claw-free graphs are perfectly orderable?, Discrete Appl. Math. 44 (1993), 39-63.
102. In praise of Claude Berge, Discrete Math. 165-166 (1997), 3-9.
103. Resolution search, Discrete Appl. Math. 73 (1997), 81-99. (An abstract is here.)
     • citations from Google Scholar
104. Variations on a theorem of Ryser (joint with D.Cao, A.J.Hoffman, and A.Vince), Linear Algebra Appl. 260 (1997), 215-222.
105. On the solution of traveling salesman problems (joint with D. Applegate, R. Bixby, and W. Cook), Documenta Mathematica Special Volume: Proceedings of the International Congress of Mathematicians (1998) 645-656.
     • Beale-Orchard-Hays Prize for Excellence in Computational Mathematical Programming
       • MPS Prizes (page 3 of Optima 65, May 2001)
     • citations from Google Scholar
     • A Generic Parallel Branch and Bound Environment on a Network of Workstations by Roman Batoukov and Tor Sørevik (published in Proceedings of HiPer'99, pp. 474-483)
106. Recognizing dart-free perfect graphs (joint with J. Fonlupt, L. Sun, and A. Zemirline) SIAM Journal on Computing 31 (2002), 1315-1338. An extended abstract appeared earlier in the Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (January 2000), pp. 50-53.
107. A bibliography on perfect graphs, in Perfect Graphs (J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 329-358.
108. TSP cuts which do not conform to the template paradigm (joint with D. Applegate, R. Bixby, and W. Cook). In Computational combinatorial optimization: optimal or provably near optimal solutions (Lecture Notes in Computer Science; 2241), Michael Jünger and Denis Naddef, eds., Springer, 2001, pp. 261--303.
     • citations from Google Scholar
109. Dirac-type characterizations of graphs without long chordless cycles (joint with I. Rusu and R. Sritharan), Discrete Math. 256 (2002), 445-448.
110. Claude Berge: 5.6.1926 -- 30.6.2002. Graphs and Combinatorics 19 (2003), 1-6.
111. Implementing the Dantzig-Fulkerson-Johnson Algorithm for Large Traveling Salesman Problems (joint with D. Applegate, R. Bixby, and W. Cook). Mathematical Programming 97 (2003) 91 - 153.
     • citations from Google Scholar
112. Sylvester-Gallai theorem and metric betweenness. Discrete & Computational Geometry 31 (2004) 175 - 195.
     • Xiaomin Chen's proof of the conjecture
113. Problems related to a de Bruijn - Erdős theorem (joint with X. Chen), Discrete Applied Mathematics 156 (2008), 2101 - 2108. (arXiv:math/0610036v1 [math.CO].)
114. Remembering Leo Khachiyan, Discrete Applied Mathematics 156 (2008), 1961 - 1962.
115. Certification of an optimal TSP tour through 85,900 cities (joint with D. Applegate, R. Bixby, W. Cook, D. Espinoza, M. Goycoolea, and K. Helsgaun) Operations Research Letters 37 (2009), 11 - 15.
116. Antimatroids, betweenness, convexity, in: William Cook, László Lovász, Jens Vygen (Editors), Research Trends in Combinatorial Optimization, Springer, Berlin 2009, pp. 57 -- 64.
117. Another abstraction of the Erdős-Szekeres Happy End Theorem (joint with N. Alon, E. Chiniforooshan, and F. Genest), The Electronic Journal of Combinatorics 17 (2010), #N11 (6 pages)
118. Comparison of two techniques for proving nonexistence of strongly regular graphs, Graphs and Combinatorics 27 (2011), 171 - 175. arXiv:0906.5389v1 [math.CO]
119. A de Bruijn - Erdős theorem and metric spaces (joint with Ehsan Chiniforooshan), Discrete Mathematics & Theoretical Computer Science Vol 13 No 1 (2011), 67 - 74.
120. Finite Sholander trees, trees, and their betweennes (joint with Dieter Rautenbach and Philipp Matthias Schäfer), Discrete Mathematics 311 (2011) 2143 - 2147. arXiv:1101.2957v1 [math.CO]
121. On Reichenbach's causal betweenness (joint with Baoyindureng Wu), Erkenntnis 76 (2012), 41 - 48. arXiv:0902.1763v1 [math.CO].

Manuscripts and technical reports

1. Selected combinatorial research problems (joint with D.A. Klarner and D.E. Knuth), STAN CS-72-292, Department of Computer Science, Stanford University, June 1972.
   • citations from Google Scholar
2. On the computational complexity of finding a kernel. Report No. CRM-300, Centre de recherches mathématiques, Université de Montréal, June 1973.
3. Rational behaviour and computational complexity, Technical Report SOCS-78.9, School of Computer Science, McGill University, November 1978.
4. Lecture notes on the new AKS sorting network. DCS-TR-294, Department of Computer Science, Rutgers University (1992).
5. Notes on the Kolakoski sequence. DIMACS TR: 93-84 (1993).
   • Dangerous Problems by Ivars Peterson
   • Elizabeth J. Kupin, Eric S. Rowland, Bounds on the frequency of 1 in the Kolakoski word, http://arxiv.org/abs/0809.2776
   • Yunbao Huang, The powers of smooth words over arbitrary 2-letter alphabets, arXiv:0904.0562v1 [math.CO]
   • Yun Bao Huang and William D. Weakley, A note on the complexity of C-infinity-words, Theoretical Computer Science
6. On a conjecture of Baiou and Balinski (joint with D. Avis), DIMACS TR: 02-08.

7. Local cuts for mixed-integer programming (joint with William Cook and Daniel Espinoza). Presented at the ISMP Meeting in Rio De Janeiro, 2006.
8. Transversals in trees (joint with Victor Campos, Luc Devroye, and Perouz Taslakian), arXiv:0705.1806v1 [math.CO].
   To appear in Journal of Graph Theory.
   • Breaking Al Qaeda Cells: A Mathematical Analysis of Counterterrorism Operations (A Guide for Risk Assessment and Decision Making) by Jonathan David Farley, Studies in Conflict and Terrorism 26 (2003), 399 -- 411.
   • Toward a Mathematical Theory of Counterterrorism by Jonathan David Farley (The Proteus Monograph Series, Volume 1, Issue 2, December 2007).
9. Lines in hypergraphs (joint with Laurent Beaudou, Adrian Bondy, Xiaomin Chen, Ehsan Chiniforooshan, Maria Chudnovsky, Nicolas Fraiman, and Yori Zwols), arXiv:1112.0376v1 [math.CO].
10. A De Bruijn-Erdős theorem for chordal graphs (joint with Laurent Beaudou, Adrian Bondy, Xiaomin Chen, Ehsan Chiniforooshan, Maria Chudnovsky, Nicolas Fraiman, and Yori Zwols), arXiv:1201.6376v1 [math.CO]

Books

1. Linear Programming, W.H.Freeman, New York, 1983. Japanese translation published by Keigaku Shuppan, Tokyo, 1986.
   
   • citations from Google Scholar
   • customer reviews at Amazon.com
   • an essay written by Michael Carter
   • Robert Fourer's Linear Programming FAQ
   • J. M. Cargal's Recommended Books in the Mathematical Sciences
   • a discussion on teaching duality
   • Optimization Bookstore
2. Topics on perfect graphs. (edited jointly with C.Berge), North-Holland Mathematics Studies 88 (Annals of Discrete Math. 21), 1984.
3. Creation and Recreation: A Tribute to the Memory of Claude Berge (edited jointly with A. Bondy), Discrete Mathematics Volume 306, Issues 19-20, Pages 2293-2636 (6 October 2006)
4. The Traveling Salesman Problem: A Computational Study (joint with D. Applegate, R. Bixby, and W. Cook), Princeton Series in Applied Mathematics, February 2007.
   
   • The citation for the 2007 Frederick W. Lanchester Prize
   • citations from Google Scholar
   • Michael Trick’s Operations Research Blog
   • Review by Jakub Marecek

5. Combinatorial Optimization: Methods and Applications (editor), Volume 31 NATO Science for Peace and Security Series - D: Information and Communication Security, IOS Press, 2011.