Papers accepted to refereed international journals

  1. Z. Dvorak, D. Kral: On Planar Mixed Hypergraphs, Electronic Journal on Combinatorics 8 (1) (2001), #R35, 23 pages.
  2. Z. Dvorak, D. Kral, R. Skrekovski: Coloring Face Hypergraphs on Surfaces, European Journal on Combinatorics 26(1) (2004), 95-110.
  3. Z. Dvorak, T. Kaiser, D. Kral: Eulerian colorings and the Bipartizing matching conjecture of Fleischner, European Journal of Combinatorics 27(7) (2006), 1088-1101.
  4. Z. Dvorak, D. Kral, O. Pangrac: Locally consistent constraint satisfaction problems, Theoretical Computer Science 348(2-3) (2005), 187-206.
  5. Z. Dvorak, R. Skrekovski: A Theorem About a Contractible and Light Edge, SIAM Journal on Discrete Mathematics 20(1) (2006), 55-61.
  6. Z. Dvorak, V. Jelinek, D. Kral, J. Kyncl, M. Saks: Probabilistic Strategies for the Partition and Plurality Problems, Random Structures & Algorithms 30(1-2) (2007), 63 - 77.
  7. Z. Dvorak, R. Skrekovski, T. Valla: Four Gravity Results, Discrete Mathematics 207(2) (2007), 181-190.
  8. J. Cerny, Z. Dvorak, V. Jelinek, J. Kara: Noncrossing Hamiltonian Paths in Geometric Graphs, Discrete Applied Mathematics 155(9) (2007), 1096-1105.
  9. Z. Dvorak, D. Kral, P. Nejedly, R. Skrekovski: Coloring squares of planar graphs with girth six, European Journal of Combinatorics 29(4) (2007), 838-849.
  10. Z. Dvorak, R. Skrekovski, M. Tancer: List-Coloring Squares of Sparse Subcubic Graphs, SIAM Journal on Discrete Mathematics 22(1) (2008), 139-159.
  11. Z. Dvorak, R. Skrekovski, T. Valla: Planar graphs of odd-girth at least 9 are homomorphic to the Petersen graph, SIAM Journal on Discrete Mathematics 22(2) (2008), 568-591.
  12. Z. Dvorak: On Forbidden Subdivision Characterization of Graph Classes, European Journal of Combinatorics 29(5) (2008), 1321-1332.
  13. Z. Dvorak, D. Kral, P. Nejedly, R. Skrekovski: Distance constrained labelings of planar graphs with no short cycles, Discrete Applied Mathematics 157 (2009), 2634-2645.
  14. Z. Dvorak: Two-factors in Oriented Graphs with Forbidden Transitions, Discrete Mathematics 309(1) (2009), 104-112.
  15. Z. Dvorak, R. Skrekovski: k-chromatic number of graphs on surfaces, SIAM Journal on Discrete Mathematics 23(1) (2009), 477-486.
  16. Z. Dvorak, S. Jendrol, D. Kral, G. Pap: Matchings and Non-rainbow Colorings, SIAM Journal on Discrete Mathematics 23(1) (2009), 344-348.
  17. Z. Dvorak, B. Lidicky, R. Skrekovski: Planar graphs without 3-,7-, and 8-cycles are 3-choosable, Discrete Mathematics 309(20) (2009), 5899-5904.
  18. Z. Dvorak, D. Kral, R. Skrekovski: Non-Rainbow Colorings of 3-, 4- and 5-Connected Plane Graphs, Journal of Graph Theory 63(2) (2010), 129-145.
  19. Z. Dvorak, D. Kral, J. Teska: Toughness Threshold for the Existence of 2-walks in K4-minor Free Graphs, Discrete Mathematics 310(3) (2010), 642-651.
  20. Z. Dvorak, T. Kaiser, D. Kral, J.-S. Sereni: A Note on Antisymmetric Flows in Graphs, European Journal of Combinatorics 31(1) (2010), 320-324.
  21. Z. Dvorak, S. Norine: Small Graph Classes and Bounded Expansion, Journal of Combinatorial Theory, series B 100 (2010), 171-175.
  22. Z. Dvorak, K. Kawarabayashi, R. Thomas: Three-coloring triangle-free planar graphs in linear time, ACM Transactions on Algorithms 7 (2011), article no. 41.
  23. Z. Dvorak: On Recognizing Graphs by Numbers of Homomorphisms, Journal of Graph Theory 64(4) (2010), 330-342.
  24. Z. Dvorak, B. Lidicky, R. Skrekovski: 3-choosability of triangle-free planar graphs with constraints on 4-cycles, SIAM Journal on Discrete Mathematics 24 (2010), 934-945.
  25. Z. Dvorak, B. Mohar: Crossing-critical graphs with large maximum degree, Journal of Combinatorial Theory, Series B 100(4) (2010), 413-417.
  26. H. Ardal, Z. Dvorak, V. Jungic, T. Kaiser: On a Rado Type Problem for Homogeneous Second Order Linear Recurrences, Electronic Journal of Combinatorics 17 (2010), #R38.
  27. Z. Dvorak, B. Mohar: Spectral radius of finite and infinite planar graphs and of graphs of bounded genus, Journal of Combinatorial Theory, series B 100(6) (2010), 729-739.
  28. Z. Dvorak, B. Lidicky, R. Skrekovski: Randić index and the diameter of a graph, European Journal of Combinatorics 32 (2011), 434-442.
  29. Z. Dvorak, A. C. Giannopoulou, D. M. Thilikos: Forbidden Graphs for Tree-depth, European Journal of Combinatorics 33 (2012), 969-979.
  30. Z. Dvorak, B. Lidicky, R. Skrekovski: Graphs with two crossings are 5-choosable, SIAM Journal on Discrete Mathematics 25 (2011), 1746-1753.
  31. Z. Dvorak, D. Kral: Classes of graphs with small rank decompositions are χ-bounded, European Journal of Combinatorics 33 (2012), 679-683.
  32. Z. Dvorak, B. Mohar, R. Samal: Star chromatic index, Journal of Graph Theory 72 (2013), 313-326.
  33. Z. Dvorak, B. Mohar: Chromatic number and complete graph substructures for degree sequences, Combinatorica 33 (2013), 513-529.
  34. Z. Dvorak, B. Lidicky, R. Skrekovski: Bipartizing fullerenes, European Journal of Combinatorics 33 (2012), 1286-1293.
  35. Z. Dvorak, B. Mohar: Spectrally degenerate graphs: Hereditary case, Journal of Combinatorial Theory, series B 102 (2012), 1099-1109.
  36. Z. Dvorak, D. Kral, R. Thomas: Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle, Journal of Combinatorial Theory, Series B 120 (2016), 1-17.
  37. Z. Dvorak: Constant-factor approximation of domination number in sparse graphs, European Journal of Combinatorics 34 (2013), 833-840.
  38. Z. Dvorak, L. Esperet: Distance-two coloring of sparse graphs, European Journal of Combinatorics 36 (2014), 406-415.
  39. A. Asadi, Z. Dvorak, L. Postle, R. Thomas: Sub-exponentially many 3-colorings of triangle-free planar graphs, Journal of Combinatorial Theory, series B 103 (2013), 706-712.
  40. Z. Dvorak, D. Kral, R. Thomas: Testing first-order properties for subclasses of sparse graphs, Journal of the ACM 60 (2013), article 36.
  41. Z. Dvorak: 3-choosability of planar graphs with (4)-cycles far apart, Journal of Combinatorial Theory, series B 104 (2014), 28-59.
  42. Z. Dvorak, T. Klimosova: Strong immersions and maximum degree, SIAM Journal on Discrete Mathematics 28 (2014), 177-187.
  43. Z. Dvorak, J.-S. Sereni, J. Volec: Subcubic triangle-free graphs have fractional chromatic number at most 145, Journal of the London Mathematical Society 89 (2014), 641-662.
  44. Z. Dvorak, B. Lidicky: 4-critical graphs on surfaces without contractible (4)-cycles, SIAM Journal on Discrete Mathematics 28 (2014), 521-552.
  45. O. Borodin, Z. Dvorak, A. Kostochka, B. Lidicky, M. Yancey: Planar 4-critical graphs with four triangles, European Journal of Combinatorics 41 (2014), 138-151.
  46. M. DeVoss, Z. Dvorak, J. Fox, J. McDonald, B. Mohar, D. Scheide: Minimum degree condition forcing complete graph immersion, Combinatorica 34 (2014), 279-298.
  47. Z. Dvorak, B. Lidicky: 3-coloring triangle-free planar graphs with a precolored 8-cycle, Journal of Graph Theory 80 (2015), 98-111.
  48. Z. Dvorak, J.-S. Sereni, Jan Volec: Fractional coloring of triangle-free planar graphs, Electronic Journal of Combinatorics 22 (2015), #P4.11.
  49. Z. Dvorak, B. Mohar: Crossing number of periodic graphs, Journal of Graph Theory 83 (2016), 34-43.
  50. Z. Dvorak, L. Postle: Density of 52-critical graphs, accepted to Combinatorica.
  51. Z. Dvorak, K. Kawarabayashi, D. Kral: Packing six T-joins in plane graphs, Journal of Combinatorial Theory, series B 116 (2016), 287-305.
  52. Z. Dvorak: Sublinear separators, fragility and subexponential expansion, European Journal of Combinatorics 52 (2016), 103-119.
  53. M. Chudnovsky, Z. Dvorak, T. Klimosova, P. Seymour: Immersion in four-edge-connected graphs, Journal of Combinatorial Theory, Series B 116 (2016), 208-218.
  54. Z. Dvorak, S. Norin: Strongly sublinear separators and polynomial expansion, SIAM J. Discrete Math. 30 (2016), 1095-1101.
  55. Z. Dvorak, B. Lidicky, B. Mohar, L. Postle: 5-list-coloring planar graphs with distant precolored vertices, Journal of Combinatorial Theory, Series B 122 (2017), 311-352.
  56. Z. Dvorak, M. Mnich: Large Independent Sets in Triangle-Free Planar Graphs, SIAM Journal on Discrete Mathematics 31 (2017), 1355-1373.
  57. Z. Dvorak, B. Lidicky, B. Mohar: 5-choosability of graphs with crossings far apart, Journal of Combinatorial Theory, Series B 123 (2017), 54-96.
  58. Z. Dvorak, B. Lidicky: Fine structure of 4-critical triangle-free graphs II. Planar triangle-free graphs with two precolored 4-cycles, SIAM J. Discrete Math. 31 (2017), 865-874.
  59. Z. Dvorak, P. Wollan: A structure theorem for strong immersions, Journal of Graph Theory 83 (2016), 152-163.
  60. Z. Dvorak, K. Kawarabayashi: Triangle-free graphs of tree-width t are (t + 3)2-colorable, European Journal in Combinatorics 66 (2017), 95-100.
  61. Z. Dvorak, L. Postle: Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, accepted to Journal of Combinatorial Theory, Series B.
  62. Z. Dvorak: Induced subdivisions and bounded expansion, accepted to European Journal in Combinatorics.
  63. Z. Dvorak, J.-S. Sereni: Do triangle-free planar graphs have exponentially many 3-colorings?, Electronic Journal of Combinatorics 24 (2017), #P3.47.

Papers presented at international conferences

  1. Z. Dvorak, J. Kara, D. Kral, O. Pangrac: On Pattern Coloring of Cycle Systems, Proceedings 28th International Workshop on Graph-Theoretic Concepts (WG’02), Lecture Notes in Computer Science vol. 2573, p. 164-175, Springer-Verlag, 2002.
  2. Z. Dvorak: New Loop Optimizer for GCC, First Annual GCC Developers’ Summit, 2003.
  3. J. Cerny, Z. Dvorak, V. Jelinek, J. Kara: Noncrossing Hamiltonian Paths in Geometric Graphs, Proceedings 11th International Symposium on Graph Drawing, Lecture Notes in Computer Science vol. 2912, Springer-Verlag, 2004.
  4. Z. Dvorak, J. Kara, D. Kral, O. Pangrac: An Algorithm for Cyclic Edge Connectivity of Cubic Graphs, Proceedings 9th Scandinavian Workshop on Algorithm Theory (SWAT’04), Lecture Notes in Computer Science vol. 3111, p. 236-247, Springer-Verlag, 2004.
  5. Z. Dvorak, D. Kral, O. Pangrac: Locally consistent constraint satisfaction problems, Proceedings 31st International Colloquium Automata, Languages and Programming (ICALP’04), Lecture Notes in Computer Science vol. 3142, p. 469-480, Springer-Verlag, 2004.
  6. Z. Dvorak: Declarative world inspiration, Second Annual GCC Developers’ Summit, 2004.
  7. Z. Dvorak, V. Jelinek, D. Kral, J. Kyncl, M. Saks: Three optimal algorithms for balls of three colors, Proceedings of 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS’05), Lecture Notes in Computer Science vol. 3404, p. 206-217, Springer-Verlag, 2005.
  8. Z. Dvorak, V. Jelinek: On the Complexity of the G-Reconstruction Problem, Proceedings of Algorithms and Computation: 16th International Symposium, ISAAC 2005, Lecture Notes in Computer Science vol. 3827, p. 196 - 205, Springer-Verlag, 2006.
  9. Z. Dvorak, D. Kral, R. Thomas: Coloring triangle-free graphs on surfaces, SODA 2009, Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms.
  10. Z. Dvorak, B. Mohar: Spectral radius of finite and infinite planar graphs and of graphs of bounded genus (extended abstract), European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), Electronic Notes in Discrete Mathematics 34 (2009), 101-105.
  11. Z. Dvorak, D. Kral: Algorithms for classes of graphs with bounded expansion, in Graph-Theoretic Concepts in Computer Science, Christophe Paul and Michel Habib (Eds.). Lecture Notes In Computer Science, Vol. 5911., Springer-Verlag, 2009.
  12. Z. Dvorak, D. Kral, R. Thomas: Deciding first-order properties for sparse graphs (Extended abstract), in Proceedings of FOCS’2010, 133-142.
  13. Z. Dvorak, K. Kawarabayashi: List-coloring embedded graphs, in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2013), 1004-1012.
  14. Z. Dvorak, V. Tuma: A dynamic data structure for counting subgraphs in sparse graphs, in Proceedings of 13th International Symposium, WADS 2013, Lecture Notes in Computer Science Volume 8037, 2013, 304-315.
  15. Z. Dvorak, M. Mnich: Large Independent Sets in Triangle-Free Planar Graphs, Algorithms – ESA 2014, Lecture Notes in Computer Science Volume 8737, 2014, 346-357.
  16. Z. Dvorak, M. Kupec, V. Tuma: A dynamic data structure for MSO properties in graphs with bounded tree-depth, Algorithms – ESA 2014, Lecture Notes in Computer Science Volume 8737, 2014, 334-345.
  17. Z. Dvorak, M. Kupec: On Planar Boolean CSP, Automata, Languages, and Programming, Lecture Notes in Computer Science Volume 9134, 2015, 432-443.
  18. Z. Dvorak, D. Kral, B. Mohar: Graphic TSP in cubic graphs, STACS’17.
  19. Z. Dvorak, B. Lidicky: Independent sets near the lower bound in bounded degree graphs, STACS’17.
  20. Z. Dvorak: Thin graph classes and polynomial-time approximation schemes, accepted to SODA’18.

Submitted and unpublished papers

  1. Z. Dvorak, J. Kara, D. Kral, O. Pangrac: Feasible Sets of Pattern Hypergraphs, available as ITI report 2002-093.
  2. J. Cerny, Z. Dvorak, V. Jelinek, and P. Podbrdsky: Generalization of the polygon-crossing problem, available as KAM-DIMATIA report 2003-623.
  3. Z. Dvorak: Eulerian tours in graphs with forbidden transitions and bounded degree, available as KAM-DIMATIA report 2004-669.
  4. Z. Dvorak: A stronger structure theorem for excluded topological minors, submitted.
  5. Z. Dvorak, R. Thomas: List-coloring apex-minor-free graphs, submitted.
  6. Z. Dvorak, D. Kral, R. Thomas: Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk, submitted.
  7. Z. Dvorak, D. Kral, R. Thomas: Three-coloring triangle-free graphs on surfaces III. Graphs of girth five, submitted.
  8. Z. Dvorak, D. Kral, R. Thomas: Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs, submitted.
  9. Z. Dvorak, D. Kral, R. Thomas: Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies, submitted.
  10. Z. Dvorak, D. Kral, R. Thomas: Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations, submitted.
  11. Z. Dvorak, D. Kral, R. Thomas: Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm, submitted.
  12. Z. Dvorak, S. Norin: Treewidth of graphs with balanced separations, submitted.
  13. Z. Dvorak, A. Kabela, T. Kaiser: Planar graphs have two-coloring number at most 8, submitted.
  14. Z. Dvorak, B. Lidicky: Fine structure of 4-critical triangle-free graphs I. Planar graphs with two triangles and 3-colorability of chains, submitted.
  15. Z. Dvorak, B. Lidicky: Fine structure of 4-critical triangle-free graphs III. General surfaces, submitted.
  16. Z. Dvorak, L. Yepremyan: Complete graph immersions and minimum degree, submitted.
  17. E. Berger, Z. Dvorak, S. Norin: Tree-width of grid subsets, submitted.
  18. Z. Dvorak, M. Hebdige, F. Hlasek, D. Kral, J. Noel: Cyclic Coloring of Plane Graphs with Maximum Face Size 16 and 17, submitted.
  19. Z. Dvorak, T. Masarik, J. Musilek, O. Pangrac: Triangle-free planar graphs with the smallest independence number, submitted.
  20. Z. Dvorak, S. Norin, L. Postle: List coloring with requests, submitted.
  21. Z. Dvorak, J. Venters: Triangle-free planar graphs with small independence number, submitted.
  22. Z. Dvorak, K. Kawarabayashi: Additive non-approximability of chromatic number in proper minor-closed classes, submitted.
  23. Z. Dvorak, T. Kelly: Induced 2-degenerate Subgraphs of Triangle-free Planar Graphs, submitted.
  24. Z. Dvorak: On classes of graphs with strongly sublinear separators, submitted.
  25. Z. Dvorak: On distance r-dominating and 2r-independent sets in sparse graphs, submitted.

Popularization papers