Tomas Kaiser

About

I am a professor at the Department of Mathematics at the Faculty of Applied Sciences of the University of West Bohemia in Pilsen. I work in combinatorics and discrete mathematics, especially graph theory. I teach courses on discrete mathematics, linear algebra, codes, logic and set theory, and organise the Graph Theory seminar at the department. I am a Managing Editor of the Journal of Graph Theory. Since 2019 I serve as a secretary of the Czech Committee for Mathematics.

I am also an editor of Innovations in Graph Theory, a diamond open access journal for high-quality research in graph theory and its interactions with other areas, launched in August 2023. We are accepting submissions now!

Contact

Publications

ORCID

Recent papers

Hypertree shrinking avoiding low degree vertices (with K. Hylasova), submitted for publication.

Packing T-connectors in graphs needs more connectivity (with R. Cada, A. Kabela and P. Vrana), submitted for publication.

Fan's lemma via bistellar moves (with M. Stehlik), submitted for publication.

Rainbow bases in matroids (with F. Horsch and M. Kriesell), to appear in SIAM J. Discrete Math..

Published papers

Criticality in Sperner's Lemma (with M. Stehlik and R. Skrekovski), Combinatorica 44 (2024), 1041-1051 (arXiv).

Quasigraphs and skeletal partitions (with P. Vrana), European J. Combin. 107 (2022), 103563 (arXiv).

Graphs of low average degree without independent transversals (with C. Groenland, O. Treffers and M. Wales), J. Graph Theory 102 (2023), 374-387 (arXiv).

Hamilton cycles in line graphs of 3-hypergraphs (with P. Vrana), Discrete Math. 345 (2022), 113028 (arXiv).

Edge-critical subgraphs of Schrijver graphs II: The general case (with M. Stehlik), J. Combin. Theory Ser. B 152 (2022), 453-482 (arXiv).

The hamiltonicity of essentially 9-connected line graphs (with P. Vrana), J. Graph Theory 97 (2021), 241-259 (arXiv).

Edge-critical subgraphs of Schrijver graphs (with M. Stehlik), J. Combin. Theory Ser. B 144 (2020), 191-196 (arXiv).

Shorter signed circuit covers of graphs (with R. Lukotka, E. Macajova and E. Rollova), J. Graph Theory 92 (2019), 39-56 (arXiv)

Decomposing planar cubic graphs (with A. Hoffmann-Ostenhof and K. Ozeki), J. Graph Theory 88 (2018), 631-640 (arXiv).

Weak regularity and finitely forcible graph limits (with J. Cooper, D. Kral and J. Noel), Trans. Amer. Math. Soc. 370 (2018), 3833-3864 (arXiv).

Planar graphs have two-coloring number at most 8 (with Z. Dvorak and A. Kabela), J. Combin. Theory Ser. B 130 (2018), 144-157 (arXiv).

Schrijver graphs and projective quadrangulations (with M. Stehlik), in: A Journey Through Discrete Mathematics: A Tribute to Jiri Matousek (M. Loebl, J. Nesetril, R. Thomas, eds.), Springer, 2017, pp. 505-526 (arXiv).

Fractional covers and matchings in families of weighted d-intervals (with R. Aharoni and S. Zerbib), Combinatorica 37 (4) (2017), 555-572 (arXiv).

Nowhere-zero flows in signed graphs: A survey (with R. Lukotka and E. Rollova), Lecture Notes of Seminario Interdisciplinare di Matematica XIV (2017), 85-104, Universita degli Studi della Basilicata (arXiv).

Treelike snarks (with M. Abreu, D. Labbate and G. Mazzuoccolo), Electron. J. Combin. 23 (3) (2016), #P3.54 (arXiv).

First order limits of sparse graphs: Plane trees and path-width (with J. Gajarsky, P. Hlineny, D. Kral, M. Kupec, J. Obdrzalek, S. Ordyniak and V. Tuma), Random Structures and Algorithms 50 (2017) (4), 612-635 (arXiv).

10-tough chordal graphs are hamiltonian (with A. Kabela), J. Combin. Theory Ser. B 122 (2017), 417--427 (arXiv).

Nowhere-zero flows in signed series-parallel graphs (with E. Rollova), SIAM J. Discrete Math. 30 (2) (2016), 1248-1258 (arXiv).

10-Gabriel graphs are Hamiltonian (with M. Saumell and N. Van Cleemput), Inf. Proc. Letters 115 (11) (2015), 877-881 (arXiv).

Colouring quadrangulations of projective spaces (with M. Stehlik), J. Combin. Theory Ser. B 113 (2015), 1-17 (arXiv).

Strong parity vertex coloring of plane graphs (with O. Rucky, M. Stehlik and R. Skrekovski), Discrete Math. Theor. Comp. Sci. 16 (2014), 143-158.

Replication in critical graphs and the persistence of monomial ideals (with M. Stehlik and R. Skrekovski), J. Combin. Theory Ser. A 123 (2014), 239-251 (arXiv).

On 1-Hamilton-connected claw-free graphs (with Z. Ryjacek and P. Vrana), Discrete Math. 321 (2014), 1-11 (preprint).

The distance-t chromatic index of graphs (with R. Kang), Combinatorics, Probability and Computing 23 (2014), 90-101 (arXiv).

The fractional chromatic number of triangle-free subcubic graphs (with D. Ferguson and D. Kral), European J. Combin. 35 (2014), 184-220 (arXiv).

Limits of near-coloring of sparse graphs (with P. Dorbec, M. Montassier and A. Raspaud), J. Graph Theory 75 (2014), 191-202.

Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs, journal version (with H. Broersma, J. Fiala, P. A. Golovach, D. Paulusma and A. Proskurowski), J. Graph Theory 79 (4) (2015), 282-299.

Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs (with H. Broersma, J. Fiala, P. A. Golovach, D. Paulusma and A. Proskurowski), Graph-Theoretic Concepts in Computer Science, LNCS 8165 (2013), 127-138 (arXiv).

Multiple Petersen subdivisions in permutation graphs (with J.-S. Sereni and Z. Yilma), Electron. J. Combin. 20 (1) (2013), #P37 (arXiv).

The rainbow connection number of 2-connected graphs (with J. Ekstein, P. Holub, M. Koch, S. Matos Camacho, Z. Ryjacek and I. Schiermeyer), Discrete Math. 313 (2013), 1884-1892 (arXiv).

A Dirac theorem for trestles (with S. Jendrol, Z. Ryjacek and I. Schiermeyer), Discrete Math. 312, 12-13 (2012), 2000-2004 (preprint).

A short proof of the tree-packing theorem, Discrete Math. 312 (2012), 1689-1691 (arXiv).

On the 2-resonance of fullerenes (with M. Stehlik and R. Skrekovski), SIAM J. Discrete Math. 25 (2011), 1737-1745.

Covering a graph by forests and a matching (with M. Montassier and A. Raspaud), SIAM J. Discrete Math. 25 (2011), 1804-1811 (arXiv).

Hamilton cycles in 5-connected line graphs (with P. Vrana), European J. Combin. 33 (2012), 924-947 (arXiv).

Star subdivisions and connected even factors in the square of a graph (with J. Ekstein, P. Holub, L. Xiong and S. Zhang), Discrete Math. 312 (2012), 2574-2578 (arXiv).

Graphs with odd cycle lengths 5 and 7 are 3-colorable (with O. Rucky and R. Skrekovski), SIAM J. Discrete Math. 25 (2011), 1069-1088.

Fractional total colourings of graphs of high girth (with A. King and D. Kral), J. Combin. Theory Ser. B 101 (2011), 383-402.

Equipartite polytopes (with B. Grunbaum, D. Kral and M. Rosenfeld), Israel J. Math. 179 (2010), 235-252.

On a Rado type problem for homogeneous second order linear recurrences (with H. Ardal, Z. Dvorak and V. Jungic), Electr. J. Comb. 17 (1) (2010), #R38.

Short cycle covers of graphs with minimum degree three (with D. Kral, B. Lidicky, P. Nejedly and R. Samal), SIAM J. Discrete Math. 24 (2010), 330-355.

Perfect matchings with restricted intersection in cubic graphs (with A. Raspaud), European J. Comb. 31 (2010), 1307-1315.

Disjoint Hamilton cycles in the star graph (with R. Cada, M. Rosenfeld and Z. Ryjacek), Information Processing Letters 110 (2009), 30-35.

A note on antisymmetric flows in graphs (with Z. Dvorak, D. Kral and J.-S. Sereni), European J. Comb. 31 (2010), 320-324.

A note on edge-colourings avoiding rainbow K₄ and monochromatic K_m (with V. Jungic and D. Kral), Electr. J. Comb. 16 (1) (2009), #N19.

Equipartite graphs (with B. Grunbaum, D. Kral and M. Rosenfeld), Israel J. Math. 168 (2008), 431-444.

Minors of simplicial complexes, Discrete Appl. Math. 157 (2009), 2597-2602.

Disjoint T-paths in tough graphs, J. Graph Theory 59 (2008), 1-10.

Cycles intersecting edge-cuts of prescribed sizes (with R. Skrekovski), SIAM J. Discrete Math. 22 (2008), 861-874.

Contractible subgraphs, Thomassen's conjecture and the dominating cycle conjecture for snarks (with H. Broersma, G. Fijavz, R. Kuzel, Z. Ryjacek and P. Vrana), Discrete Math. 308 (2008), 6064-6077.

Neighborhood unions and extremal spanning trees (with E. Flandrin, R. Kuzel, H. Li and Z. Ryjacek), Discrete Math. 308 (2008), 2343-2350.

Hamilton cycles in prisms (with D. Kral, M. Rosenfeld, Z. Ryjacek and H.-J. Voss), J. Graph Theory 54 (2007), 249-269.

Short disjoint paths in locally connected graphs (with C. Chen, R. Cada and Z. Ryjacek), Graphs Comb. 23 (2007), 509-519.

A note on k-walks in bridgeless graphs (with R. Kuzel, H. Li and G. Wang), Graphs Comb., 23 (2007), 303-308.

Tough spiders (with D. Kral and L. Stacho), J. Graph Theory 56 (2007), 23-40.

T-joins intersecting small edge-cuts in graphs (with R. Skrekovski), J. Graph Theory 56 (2007), 64-71.

The circular chromatic number of graphs of high girth (with D. Kral, R. Skrekovski a X. Zhu), J. Combin. Theory Ser. B 97 (2007), 1-13.

Unions of perfect matchings in cubic graphs (with D. Kral and S. Norine), Topics in Discrete Mathematics, Algorithms Combin. 26, Springer, Berlin, 2006, pp. 225-230.

Eulerian colorings and the Bipartizing Matchings Conjecture of Fleischner (with Z. Dvorak and D. Kral), European J. Comb. 27 (2006), 1088-1101.

A note on interconnecting matchings in graphs, Discrete Math. 306 (2006), 2245-2250.

On the pancyclicity of lexicographic products (with M. Kriesell), Graphs Comb. 22 (2006), 51-58.

The prism over the middle-levels graph is hamiltonian (with P. Horak, M. Rosenfeld a Z. Ryjacek), Order 22 (2005), 73-81.

Hourglasses and Hamilton cycles in 4-connected claw-free graphs (with M. Li, Z. Ryjacek and L. Xiong), J. Graph Theory 48 (2005), 267-276.

Hamiltonian decompositions of prisms over cubic graphs (with R. Cada, M. Rosenfeld and Z. Ryjacek), Discrete Math. 286 (2004), 45-56.

A revival of the Girth Conjecture (with D. Kral and R. Skrekovski), J. Combin. Theory Ser. B 92 (2004), 41-53.

Planar graph colorings without short monochromatic cycles (with R. Skrekovski), J. Graph Theory 46 (2004), 25-38.

On growth rates of closed permutation classes (with M. Klazar), Electr. J. Comb. 9, 2 (2003), #R10.

Line transversals to unit disks, Discrete Comput. Geom. 28 (2002), 379-387.

Intersection properties of families of convex (n,d)-bodies (with Yu. Rabinovich), Discrete Comput. Geom. 21 (1999), 275-287.

Piercing problems and topological methods. Ph.D. Thesis, Charles University, Prague, 1998.

Transversals of d-intervals, Discrete Comput. Geom. 18 (1997), 195-203.

A sufficient condition of full normality, Comment Math. Univ. Carolinae 37, 2 (1996), 381-389.

Notes and extended abstracts

Some problems on even factors in graphs, Midsummer Combinatorial Workshop 2011, Praha.

Contractible subgraphs, Thomassen's conjecture and the dominating cycle conjecture for snarks (with H. Broersma, G. Fijavz, R. Kuzel, Z. Ryjacek and P. Vrana), 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications (Prague, 2006), Electronic Notes in Discrete Mathematics 28 (2007), 55-59.

Non-intersecting perfect matchings in cubic graphs (Extended Abstract) (with A. Raspaud), 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications (Prague, 2006), Electronic Notes in Discrete Mathematics 28 (2007), 293-299.

Some problems on matchings and toughness, Midsummer Combinatorial Workshop 2005, Prague.

Cycles intersecting edge-cuts of specified sizes (Extended abstract) (with R. Skrekovski), Eurocomb 2005, Berlin.

Unions of perfect matchings in cubic graphs (Extended abstract) (with D. Kral and S. Norine), 7th French International Colloquium on Graph Theory, 2005.

Eulerian colorings and Fleischner's Bipartizing matchings conjecture (Extended abstract) (with Z. Dvorak and D. Kral), Eurocomb '03, Prague.

Tutte trails, Midsummer Combinatorial Workshop 2002, Prague.