Vašek Chvátal's list of publications

(with a few links to related web pages).

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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  38. Longest common subsequences of two random sequences (joint with D. Sankoff), J.Appl.Probab. (1975), 306-315.
  39. A combinatorial theorem in plane geometry, J.Combin.Theory 18 (1975), 39-41.
  40. On certain polytopes associated with graphs, J.Combin.Theory 18 (1975), 138-154.
  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.
  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.
  47. Aggregation of inequalities in integer programming (joint with P.L. Hammer), Ann.Discrete Math. 1 (1977), 145-162.
  48. Determining the stability number of a graph, SIAM J.Comput. 6 (1977), 643-662.
  49. Distances in orientations of graphs (joint with C.Thomassen), J. Combin.Theory Ser.B 24 (1978), 61-75.
  50. Biased positional games (joint with P.Erdős), Ann.Discrete Math. 2 (1978), 221-229.
  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.
  53. The tail of the hypergeometric distribution, Discrete Math. 25 (1979), 285-287.
  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.
  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.
  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.
  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.
  72. Mastermind, Combinatorica 3 (1983), 325-329.
  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.
  82. On the P4-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 P4-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.
  89. Many hard examples for resolution (joint with E.Szemerédi), J.Assoc.Comput.Mach. 35 (1988), 759-768.
  90. On cutting-plane proofs in combinatorial optimization (joint with W. Cook and M.Hartmann), Linear Algebra Appl. 114/115 (1989), 455-499.
  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.
  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: ...
  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.)
  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.
  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.
  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.
  112. Sylvester-Gallai theorem and metric betweenness. Discrete & Computational Geometry 31 (2004) 175 - 195.
  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), Note #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].
  122. Transversals in trees (joint with Victor Campos, Luc Devroye, and Perouz Taslakian), Journal of Graph Theory 73 (2013), 32 -- 43. arXiv:0705.1806v1 [math.CO].
  123. Can brains generate random numbers? (joint with Mark Goldsmith), in: Physics, Computation, and the Mind - Advances and Challenges at Interfaces: Proceedings of the 12th Granada Seminar on Computational and Statistical Physics, AIP Conf. Proc. 1510, pp. 271-273.
  124. Local cuts for mixed-integer programming (joint with William Cook and Daniel Espinoza), Mathematical Programming Computation 5 (2013), 171-200.
  125. Lines in hypergraphs (joint with Laurent Beaudou, Adrian Bondy, Xiaomin Chen, Ehsan Chiniforooshan, Maria Chudnovsky, Nicolas Fraiman, and Yori Zwols), Combinatorica 33 (2013), 633-654. arXiv:1112.0376v1 [math.CO].
  126. Number of lines in hypergraphs (joint with Pierre Aboulker, Adrian Bondy, Xiaomin Chen, Ehsan Chiniforooshan, and Peihan Miao), Discrete Applied Mathematics 171 (2014) 137-140. arXiv:1308.5393 [math.CO]
  127. A De Bruijn-Erdős theorem for 1-2 metric spaces, Czechoslovak Mathematical Journal 64 (2014), 45--51. arXiv:1205.1170v1 [math.CO]
  128. 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), The Electronic Journal of Combinatorics 22, Issue 1 (2015), Paper #P1.70 (6 pages).
  129. McCulloch-Pitts brains and pseudorandom functions, joint with Mark Goldsmith and Nan Yang, Neural Computation 28 (2016), 1042--1050. arXiv:1603.01573 [math.DS]

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.
  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).
  6. Can brains generate random numbers? (joint with Mark Goldsmith), arXiv:1208.6451 [math.DS]
  7. Patterns of conjunctive forks (joint with František Matúš and Yori Zwols), arXiv:1608.03949v2 [math.PR]

Books

  1. Linear Programming, W.H.Freeman, New York, 1983. Japanese translation published by Keigaku Shuppan, Tokyo, 1986.

  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.

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

Back to Vašek Chvátal's home page