%Dear Henry, % %I am enclosing below the list of publications of Svata, %as a tex file. %As for the picture, I had seen it in Passau; if I can %reach it again I will let you know. %%All the best, Monique % %---- %==== % % % march 1, 1994 - % \documentstyle{article} \begin{document} \begin{center} %{\bf Annexe 1: LISTE DE PUBLICATIONS} { \large \bf PUBLICATION LIST} \\ \bigskip Svatopluk Poljak %Department of Applied Mathematics\\ %Faculty of Mathematics and Physics\\ %Charles University, Prague\\ \ \\ {\em February 1994} \end{center} \begin{enumerate} \item \label{p74} A note on stable sets and colouring of graphs, {\it Comment. Math. Univ. Carolinae } 15 (1974) 307--309. MR 50\# 4369; Zbl 284.05105 % 05C15 R. Halin, Autoref \item \label{bpt76} (with M. Boguszak and J. Tuma) Note on homomorphism interpolation theorem, {\it Comment. Math. Univ. Carolinae} 17 (1976) 105-109. MR 53\# 12964; Zbl 335.05007 % 05A17 W. Taylor, I.T.Jacobson \item \label{pt79a} (with D. Turz\'{\i}k) On amalgamation of graphs and essential sets of generators, {\it Comment. Math. Univ. Carolinae} 19 (1979) 359-369. MR 80a:05171; Zbl 276.05053 % 05C99 J. Nesetril, Summary \item \label{pt79b} (with D. Turz\'{\i}k) Some equivalent formulations of the intersection problem of finitelly generated classes of graphs, {\it Acta} {\it Sci}. {\it Math}. 41 (1979) 357-374. MR 81c:05035; Zbl 427.05049 % 05C10 P.Ungarn, autoref \item \label{pr80} (with V. R\"{o}dl) Orthogonal partitions and covering of graphs, {\it Czechoslovak Mathematical Journal} 105 (1980) 475-485. MR 82j:05088; Zbl 456.05051 % 05C70 (05B15) A. Pultr, autoref \item \label{pt80} (with D. Turz\'{\i}k) Weak join of matroids, {\it Proc. 8th Winter School on Abstract Analysis,} Math. Institute Czech. Acad. Sci. 1980, pp.130-133. \item \label{np80} (with J. Ne\v{s}et\v{r}il) Geometric and algebraic aspects of combinatorial optimization (in Czech), {\it SOFSEM 1980,} pp.35-77. \item \label{npt81} (with J. Ne\v{s}et\v{r}il and D. Turz\'{\i}k) Amalgamation of matroids and its applications, {\it J. Combinatorial Theory Ser.B} 31 (1981) 9-22. MR 82k:05080; Zbl 473.05021 % 05C55 J. H. Mason, I. Dragan % 1982: 1B737 Slijanije matroidov i jego prilozenija (S. Kislickin) \item \label{pr81a} (with V. R\"{o}dl) On the arc-chromatic number of a digraph, {\it J. Combinatorial Theory Ser.B} 31 (1981) 190-198. MR 82j:05059; Zbl 472.05024 % 05C15 (05C20) R. C. Entringer, dtto %1982: 3B589 O dugovo - kromaticeskom cisle orgrafa (Melnikov) \item \label{pp81a} (with A. Pultr) On the dimension of trees, {\it Discrete Mathematics} 34 (1981) 165-171. MR 82m:05040; Zbl 476.05075 % 05C05 (05C10) D. L. Goldsmith, J. Rosicky \item \label{pr81b} (with V. R\"{o}dl) On set systems determined by intersections, {\it Discrete Mathematics} 34 (1981) 173-184. MR 82e:05105; Zbl 474.05060 % 05C65 (05C75) Maria Ferro; R. Stanton \item \label{prt81} (with V. R\"{o}dl and D. Turz\'{\i}k) Complexity of representing graphs by set systems, {\it Discrete Applied Mathematics} 3 (1981) 301-312. MR 83j:68054; Zbl 473.68064 % 68C25 (05C35) auth. summary; G. Grimmet \item \label{ppr81} (with A. Pultr and V. R\"{o}dl) On the dimension of Kneser graphs, in: {\it Algebraic Methods in Graph Theory,} eds. L. Lov\'{a}sz and V. T. S\'{o}s, Colloq. Math. Soc. J{\'a}nos Bolyai 25, North-Holland, Amsterdam 1981, pp. 631-646. {\bf Zb} 476.05077 %{\bf MR} ????????? % J. Rosicky % 1982: 2B603 O razmernosti grafov knesera ( S. Kyslicyn) \item \label{pt81} (with D. Turz\'{\i}k) A note of dimension of $P_3^n,$ {\it Czechoslovak Mathematical Journal} 106 (1981) 484-487. {\bf Zb} 476.05076 %{\bf MR} ????????? % K. Lesniak-Foster % 1982: 2B605 O razmernosti P_3^n (M. Luzhkov) \item \label{pp81b} (with A. Pultr) Representing graphs by means of strong and weak products, {\it Comment. Math. Univ. Carolinae} 22 (1981) 449-466. {\bf MR} 83d:05085 {\bf Zb} 476.05074 % 05C99 B. Zelinka, J. Rosicky % 1982: 3B596 Predstavlenije grafov s pomoscju silnogo i slabogo % proizvedenij (A. Petronjuk) \item \label{ppt82} (with D. Turz\'{\i}k and P. Pudl\'{a}k) Extension of k-subsets to $k+1-subsets$ - existence versus costructability, {\it Comment. Math. Univ. Carolinae} 23 (1982) 337-349. {\bf MR} 83h:68045 {\bf Zb} 495.68059 % 68C05 auth. summary, summary \item \label{pt82a} (with D. Turz\'{\i}k) A polynomial algorithm for constructing a large bipartite subgraph with an application to satisfiability problem, {\it Canadian Mathematical J.} 24 (1982) 519-524. MR 83j:05048; Zbl 487.68058 % 05C35 (03B05, 65E10) T. Watanabe, autoref(see 471.68041) \item \label{pt82b} (with D. Turz\'{\i}k) A note on sticky matroids, {\it Discrete Mathematics} 42 (1982) 119-123. MR 84d:05059; Zbl 491.05020 % 05B35 R. Cordovil, A. Recski \item \label{ps82} (with M. Sura) An algorithm for graceful labelling of trees, {\it Ars Combinatoria} 14 (1982) 57-66. MR 84d:05150; Zbl 504.05029 % 05C99 C. Hoede; V. Malyshko \item \label{ppr83a} (with A. Pultr and V. R\"{o}dl) On qualitatively independent partitions and related problems, {\it Discrete Applied Mathematics} 6 (1983) 193-205. MR 85d:05024; Zbl 515.05009 %Katona; E. Fuchs %1984: 2B457 O katchestvenno-nezavisimych razbijenijach i smeznych zadacach % (B. Steckin) \item \label{pr83a} (with V. R\"{o}dl) On classes of graphs determined by forbidden subgraphs, {\it Czechoslovak Mathematical Journal} 108 (1983) 27-33. MR 84d:05129; Zbl 528.05054 % 05C55 (05C35) J. Spencer; R. L. Hemminger % 1983: 3B537 O klassach grafov opredelennych zaprescenymi subgrafami % (C. Jutmanov) \item \label{ps83a} (with M. Sura) On periodical behaviour in societies with symmetrical relations, {\it Combinatorica} 3 (1983) 119-121. MR 85a:90022; Zbl 561.90008 % ????? auth. summary; summary \item \label{ps83b} (with M. Sura) On a construction of graceful trees, in: {\it Graphs and Other Combinatorial Topics} (M. Fiedler ed.), Proc. of the Third Czech.Symp. on Graph Theory (Prague 1982), Teubner Texte zur Math. 59, Leipzig 1983, pp. 220-222. % MR ?????????; Zbl 528.05021 % ; M.M.Syslo \item \label{ppr83b} (with A. Pultr and V. R\"{o}dl) On a product dimension of bipartite graphs, {\it Journal of Graph Theory} 7 (1983) 475-486. MR 85i:05202; Zbl 531.05038 % ????? W.G. Brown; J. Sheenan \item \label{pt84a} (with D. Turz\'{\i}k) On systems, periods and semipositive mappings, {\it Comment. Math. Univ. Carolinae} 25 (1984) 597-614. %MR ?????????; Zbl 576.05059 % ?????; Summary \item \label{pt84b} (with D. Turz\'{\i}k) Amalgamation over uniform matroids, {\it Czechoslovak Mathematical Journal} 109 (1984) 239-246. MR 85i:05075; Zbl 553.05029 % ????? Simoes-Pereira; J.B. Oxley \item \label{pt84c} (with D. Turz\'{\i}k) Amalgamation of matroids along hypergraphs, in: {\it Finite and Infinite Sets} ( eds. A. Hajnal, L. Lov{\'a}sz and V. T. S\'{o}s), Colloq. Math. Soc. Janos Bolyai 37, North-Holland, Amsterdam 1984, pp. 607-620. MR 87a:05048; Zbl 567.05015 % ????? ; autoref \item \label{npt84} (with J. Ne\v{s}et\v{r}il and D. Turz\'{\i}k) Some remarks on the Ramsey matroids, {\it Supplemento ai Rendiconto del Circolo Matematico di Palermo, Serie II, n.3} ({\it 1984}), Proceeding of the 11th Winter School on Abstract Analysis, pp. 185-189. %MR ?????????; Zbl 543.05021 % ????? ; autoref \item \label{pt85} (with D. Turz\'{\i}k) On social influence models with ranking alternatives and local election rules, {\it Mathematical Social Sciences} 10 (1985) 189-198. \item \label{pp85} (with J. Pelant) Extensions of cyclically monotone mappings, {\it Supplemento ai Rendiconto del Circolo Matematico di Palermo, Serie II, n.11} ({\it 1985}), Proceeding of the 13th Winter School on Abstract Analysis, pp. 81-88. % MR Zbl 586.90005 % \item \label{np85} (with J. Ne\v{s}et\v{r}il) On the complexity of the subgraph problem , {\it Comment. Math. Univ. Carolinae} 26 (1985) 415-419. % MR ???:?????; Zbl 571.05050 % \item \label{npt85} (with J. Ne\v{s}et\v{r}il and D. Turz\'{\i}k) Special amalgams of matroids, in: {\it Matroid Theory,} eds. L. Lov{\'a}sz and A. Recski, Colloq. Math. Soc. J{\'a}nos Bolyai 40, North-Holland, Amsterdam 1985, pp. 267-298. MR 87k:05053 % U. Faigle \item \label{np86} (with J. Ne\v{s}et\v{r}il) A note on max-cut problem with an application to discrete-analogue convertors, {\it Operations Research Letters} 4 (1986) 289-191. Zbl 585.90085 \item \label{pt86a} (with D. Turz\'{\i}k) On an application of convexity to discrete systems, {\it Discrete Applied Mathematics} 13 (1986) 27-32. MR 87k:58133; Zbl 588.93048 % ????? Marek Grazy Zehn \item \label{pt86b} (with D. Turz\'{\i}k) On pre-periods of discrete influence systems, {\it Discrete Applied Mathematics} 13 (1986) 33-39. MR 87k:58134; % Zbl % M. Grazy Z. \item \label{pt86c} (with D. Turz\'{\i}k) A polynomial heuristic for certain subgraph optimization problems with guaranteed lower bound, {\it Discrete Mathematics} 58 (1986) 99-104. Zbl 585.05032 % ; Abstract (Z. Ma) \item \label{ppt87} (with J. Pelant and D. Turz\'{\i}k) Limit behaviour of trajectories involving subgradients of convex functions, {\it Comment. Math. Univ. Carolinae} 28 (1987) 457-466. \item \label{pt87} (with D. Turz\'{\i}k) On a facet of the balanced subgraph polytope, {\it \v {C}as. p\v {e}st. matem.} 112 (1987) 373-380. \item \label{pCh87} (with M. Chrobak) A generalization of Smith's Theorem, {\it Zastosowania Matematyki} ({\it Applic.} {\it Math.}) XIX (1987) 371-374. \item \label{pTuz87} (with Zs. Tuza) Maximum bipartite subgraphs of Kneser graphs, {\it Graphs and Combinatorics} 3 (1987) 191-199. \item \label{p87} Transformations on graphs and convexity, {\it Complex Systems} 1 (1987) 1021-1033. \item \label{lp88a} (with M. Loebl) Matroids induced by packing subgraphs, {\it J. Combinatorial Theory Ser.B} 44 (1988) 338-354. \item \label{pt88a} (with D. Turz\'{\i}k) Subgradients of convex functions and periodical behaviour of finite automata, Proc. of Inst. Chem. Tech. (Prague), M 2 (1988), 75--86. \item \label{lp88b} (with M. Loebl) On the union of matching matroids, {\it Mathematica Slovaca} 38 (1988) 301-304. \item \label{lp88c} (with M. Loebl) Bipartite packing, in: {\it Combinatorics,} Eger (Hungary) 1987, Colloq. Math. Soc. J\'anos Bolyai 52, North-Holland, Amsterdam 1988, pp. 375-384. \item \label{pCh88} (with M. Chrobak) On common edges in optimal solutions to travelling salesman and and other optimization problems, {\it Discrete Applied Mathematics} 20 (1988) 101-111. \item \label{prs88} (with V. R\"{o}dl and J. Spencer) Polynomial time algorithm for tournament ranking that ensures the expected profit, {\it SIAM J. on Discrete Mathematics,} 1 (1988) 372-376. \item \label{pTuz89} (with Zs. Tuza) Improved bounds for the number of qualitetively independent partitions, {\it J. Combinatorial Theory} {\it Ser.}A 51 (1989) 111-116. \item \label{p89} Maximum rank of powers of a matrix of a given pattern, {\it Proceedings AMS} 106 (1989) 1137-1144. \item \label{lp89} (with M. Loebl) A hierarchy of totally unimodular matrices, {\it Discrete Mathematics} 76 (1989) 241-246. \item \label{ap89} (with P. Alles) Long induced paths and cycles in Kneser graphs, {\it Graphs and Combinatorics} 5 (1989) 303-306. \item \label{p90} On the generic dimension of controllable subspaces, {\it IEEE Transactions on Automatic} {\it Control}, March 1990, Vol.35, No.3, 367-369. \item \label{lp90} (with M. Loebl) Subgraph packing - a survey. {\it Topics in Combinatorics and Graph Theory: Essays in Honour of Gerhard Ringel,} Physica-Verlag Heidelberg 1990, pp.491-503. \item \label{Mup90} (with K. Murota) Note on a graph-theoretic criterion for structural output controllability, {\it IEEE Transactions on Automatic} {\it Control} vol. 35, No 8 August 1990, 939-942. \item \label{Mop90} (with B.Mohar) Eigenvalues and the max-cut problem, {\it Czechoslovak Mathematical} {\it Journal} 40(115) (1990) 343-352. \item \label{kp90} (with M. Kano) Graphs with the Balas-Uhry property, {\it Journal of Graph Theory} 14 (1990) 623-628. \item \label{anp91} (with P. Alles and J. Ne\v{s}et\v{r}il) Extendabillity, dimensions and diagrams for cyclic orders, {\it SIAM J. on Discrete Mathematics} 4 (1991) 453-471. \item \label{ps91} (with M. Schlegel) Computing generic Jordan canonical form, {\it Linear and Multilinear Algebra} 28 (1991) 241-249. \item \label{ip91} (with T. Ibaraki) Weak three-linking in Eulerian digraphs, {\it SIAM J. on Discrete Mathematics,} 4 (1991) 84-98 \item \label{p91} Coloring digraphs by iterated antichains, {\it Comment. Math. Univ. Carolinae} 32,2 (1991) 209-212. \item \label{p91b} Polyhedral and eigenvalue approximations of the max-cut problem. in: {\it "Sets, Graphs and Numbers"} (eds. G. Hal\'asz, L. Lov\'asz, D. Mikl\'os and T. Sz\"onyi), Colloq. Math. Soc. J\'anos Bolyai 60, North-Holland, Amsterdam 1992, pp. 569-581. % report 91691-OR Bonn \item \label{lp91} (with M. Loebl) Packing by families of subgraphs, in {\em Forth Czecho\-slovakian Symposium on Combinatorics, Graph Theory and complexity}, (M. Fiedler and J. Nesetril eds.), Annals of Discrete Mathematics 51, North-Holland 1992, pp.~181--186. \item \label{clp92} (with Y. Crama and M. Loebl) On line balancing of strongly unimodular matrices, {\it Discrete Applied Mathematics}, 102 (1992) 143--147. % MR 93g:05097 05C50 13A21 Ernie S.Solheid \item \label{dlp92} (with M. Deza and M. Laurent) Facets of the cut cone III: The role of triangle facets, {\it Graphs and Combinatorics} 8 (1992) 125--142. \item \label{lp92} (with M. Laurent) The metric polytope, {\em Proc of IPCO 1992}, (eds. E. Balas, G. Cornuejols and R. Kannan), 1992, pp. 274--286. \item \label{p92} Minimum spectral radius of a weighted graph, {\it Linear Algebra and Its Applications}, 171 (1992) 53--63. % MR 93g:05098 (05c50, 05c70) Peter Rowlinson \item \label{kp92} (with J. Kratochv\'{\i}l) Compatible two-factors, {\it Discrete Applied} {\it Mathematics}, 36 (1992) 253--266. \item \label{pt92} (with D. Turz\'{\i}k) Maximum cut in circulant graphs, {\it Discrete Mathematics,} 108 (1992) 379--392. \item \label{p92b} On the gap between structural controllability of time-invariant and time-varying systems, {\it IEEE Transactions on Automatic Control}, 37 (1992) 1961--1965. %Report No. 91701-OR (Institut f\"ur Diskrete Mathematik, %Universit\"at Bonn). \item \label{dp93} (with Ch. Delorme) The performance of an eigenvalue bound in some classes of graphs, in {\it Proceedings of the Conference on Combinatorics, Marseille 1990.} {\it Discrete Mathematics}, 111 (1993) 145--156. %Report No. 91705-OR (Institut f\"ur Diskrete Mathematik, %Universit\"at Bonn), \item \label{p93} On existence theorems, in {\it Proceedings of the Conference on Combinatorics, Marseille 1990.} {\it Discrete Mathematics}, 122 (1993) 423--434. %Report No. 91697-OR (Institut f\"ur Diskrete Mathematik, %Universit\"at Bonn), \item \label{mp93} (with B. Mohar) Eigenvalue methods in combinatorial optimization, in: {\em Combinatorial and Graph-Theoretic Problems in Linear Algebra}, (eds. R. Brualdi, S. Friedland and V. Klee), The IMA Volumes in Mathematics and its Applications, vol. 50, Springer-Verlag 1993, pp. 107--151. \item \label{bp?} (with J. Bang-Jensen) Eulerian trails through a set of terminals in specific, unique and all orders. In: "Graph Structure Theory", Proc. AMS-IMS-SIAM Joint Summer Conf. (Seattle 1991), eds. N.~Robertson and P.~Seymour, Contemporary Mathematics vol.~147, Amer. Mat. Soc. 1993, pp. 247--258. %Report No. 92750-OR (Institut f\"ur Diskrete Mathematik, %Universit\"at Bonn). \item \label{dp?b} (with Ch. Delorme) Combinatorial properties and the complexity of an eigenvalue approximation of the max-cut problem, Europ. J. Combinatorics 14 (1993) 313--333. %Report No. 91687-OR (Institut f\"ur Diskrete Mathematik, %Universit\"at Bonn), \item \label{pRohn} (with J. Rohn) Checking robust nonsingularity is NP-hard, {\it Mathematics of Control, Signals and Systems} 6 (1993) 1--9. %Report No. 92758-OR (Institut f\"ur Diskrete Mathematik, %Universit\"at Bonn). \item \label{hmpr93} (with Ch. Helmberg, B. Mohar, and F. Rendl) A spectral approach to bandwidth and separator problems in graphs, Third IPCO Conference (G. Rinaldi and L. Wolsey, eds.), 1993 pp. 183--194. % submitted for the special issue LAMA (Edinburgh Workshop) \item \label{lp?a} (with M. Loebl) Efficient subgraph packing. {\it J. Combinatorial Theory Ser.B}, 59 (1993) 106--121. \item \label{dp?a} (with Ch. Delorme) Laplacian eigenvalues and the maximum cut problem, {\em Mathematical Programming} 63 (1993) 557--574. \item \label{np?} (with T.Nishizeki) K-connectivity and decomposition of graphs into forests, {\it Discrete Applied Mathematics}, 55 (1994) 295-301. \item \label{pTuz?} (with Zs. Tuza) Bipartite subgraphs of triangle free graphs, SIAM J. Discrete Math. 7 (1994) 307--314. %Report No. 91686-OR (Institut f\"ur Diskrete Mathematik, %Universit\"at Bonn), \item \label{pr?e} (with F. Rendl) Computational experiments with node and edge relaxations of the max-cut problem, Computing 52 (1994) 123--137. \item \label{pTuz?a} (with Zs. Tuza) On the expected relative error of the polyhedral approximation of the max-cut, {\em Oper. Res. Letters} 16 (1994) 191-198. %Report No. 92757-OR (Institut f\"ur Diskrete Mathematik, %Universit\"at Bonn), \item \label{pr?b} (with F. Rendl) Computing the max-cut by eigenvalues, to appear in a special volume of {\it Annals of Operation Research}. %Report No. 91735-OR (Institut f\"ur Diskrete Mathematik, %Universit\"at Bonn) \item \label{pr?} (with F. Rendl) Nonlinear relaxation of the graph-bisection problems, to appear in SIAM J. Opt. % Dimacs Technical Report 92-55 \item \label{hmpr93a} (with Ch. Helmberg, B. Mohar, and F. Rendl) A spectral approach to bandwidth and separator problems in graphs, to appear in {\em Linear and Multilinear Algebra}. \item \label{hhp?} (with G. Hahn and P. Hell) On the ultimate independence ratio of a graph, Report No. 91717-OR (Institut f\"ur Diskrete Mathematik, Universit\"at Bonn), Europ. J. Combinatorics 16 (1995). to appear. \item \label{lp?e} (with M. Laurent) One-third integrality in the metric polytope, Mathematical Programming, 71 (1996) 29-50. \item \label{p?} Integer linear programs and local search, SIAM J. Comp. 24 (1995) 822-839. \item \label{wr?} (with H. Wolkowicz) Convex relaxations of 0-1 quadratic programming, {Mathematics of Operation Research}, 20:550--561, 1995. %(Academia Sinica 1993), %Dimacs Technical Report 93-18, \item \label{lp?f} (with M. Laurent) On a positive semidefinite relaxation of the cut polytope, Linear Algebra and Its Applications, 223/224:439--461, 1995. %sumbitted to LAA \item \label{pt?} (with Zs. Tuza) Max-cut -- a survey, preprint Academia Sinica, 1993. \item \label{pt95} (with Zs. Tuza) Maximum cuts and largest bipartite subgraphs. In W.~Cook, L.~Lov\'asz, and P.~Seymour, editors, {\em Combinatorial Optimization}, volume~20 of {\em DIMACS Series in Discrete Mathematics and Theoretical Computer Science}, pages 181--244. American Mathematical Society, 1995. \item (with M. Laurent) On the facial structure of the correlation matrices, SIAM J. Matrix Analysis, 17:530--547, 1996. \item (with M. Laurent and F. Rendl) Connections between semidefinite relaxations of the max-cut and stable set problems, Mathematical Programming, to appear. \item \label{prw1} (with F. Rendl and H. Wolkowicz) A recipe for semidefinite relaxation for (0,1)-quadratic programming, J. Global Optimization, 7:51--73, 1995. \item (with M. Laurent) On the gap inequalities Europ. J. Comb., 1996, to appear. \item \label{ptur} (with D. Turzik) The probability of exact graphs, in preparation. \item \label{hprw1} (with C. Helmberg, F. Rendl and H. Wolkowicz) A semidefinite programming approach to integer programming, Proceedings of the 4th International IPCO Conference, Egon Balas and Jens Clausen (Eds.), Lecture Notes in Computer Science 920, Springer 1995, pp. 124-134. \item \label{p?a} Neural Networks via Convexity and Linear Programming, submitted \item \label{dp?d} (with Ch. Delorme) Nonlinear relaxation of graph partition problems, in preparation. \item \label{pRod?} (with V.R\"{o}dl) Average discrepancy of a set system, in preparation. \item \label{DHPRR} (with C. DeSimone, Ch. Helmberg, F. Rendl and G. Rinaldi) Polyhedral and semidefinite relaxations for the max-cut problem, in preparation. \end{enumerate} \end{document}