Source author record

Tomáš Kaiser

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Geometry Data Structures and Algorithms

Catalog footprint

Research overview

19works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Graphs of low average degree without independent transversals

An independent transversal of a graph $G$ with a vertex partition $\mathcal P$ is an independent set of $G$ intersecting each block of $\mathcal P$ in a single vertex. Wanless and Wood proved that if each block of $\mathcal P$ has size at least $t$ and the average degree of vertices in each block is at most $t/4$ , then an independent transversal of $\mathcal P$ exists. We present a construction showing that this result is optimal: for any $\varepsilon > 0$ and sufficiently large $t$ , there is a family of forests with vertex partitions whose block size is at least $t$ , average degree of vertices in each block is at most $(\frac14+\varepsilon)t$ , and there is no independent transversal. This unexpectedly shows that methods related to entropy compression such as the Rosenfeld-Wanless-Wood scheme or the Local Cut Lemma are tight for this problem. Further constructions are given for variants of the problem, including the hypergraph version.

preprint2022arXiv

Hamilton cycles in line graphs of 3-hypergraphs

We prove that every 52-connected line graph of a rank 3 hypergraph is Hamiltonian. This is the first result of this type for hypergraphs of bounded rank other than ordinary graphs.

preprint2022arXiv

Quasigraphs and skeletal partitions

We give a new proof of the Skeletal Lemma, which is the main technical tool in our paper on Hamilton cycles in line graphs [T. Kaiser and P. Vrána, Hamilton cycles in 5-connected line graphs, European J. Combin. 33 (2012), 924-947]. It generalises results on disjoint spanning trees in graphs to the context of 3-hypergraphs. The lemma is proved in a slightly stronger version that is more suitable for applications. The proof is simplified and formulated in a more accessible way.

preprint2019arXiv

Edge-critical subgraphs of Schrijver graphs

For $k\geq 1$ and $n\geq 2k$ , the Kneser graph $KG(n,k)$ has all $k$ -element subsets of an $n$ -element set as vertices; two such subsets are adjacent if they are disjoint. It was first proved by Lovász that the chromatic number of $KG(n,k)$ is $n-2k+2$ . Schrijver constructed a vertex-critical subgraph $SG(n,k)$ of $KG(n,k)$ with the same chromatic number. For the stronger notion of criticality defined in terms of removing edges, however, no analogous construction is known except in trivial cases. We provide such a construction for $k=2$ and arbitrary $n\geq 4$ by means of a nice explicit combinatorial definition.

preprint2019arXiv

The hamiltonicity of essentially 9-connected line graphs

Yang et al. proved that every 3-connected, essentially 11-connected line graph is Hamilton-connected. This was extended by Li and Yang to 3-connected, essentially 10-connected graphs. Strengthening their result further, we prove that 3-connected, essentially 9-connected line graphs are Hamilton-connected. We use a method based on quasigraphs in combination with the discharging technique. The result extends to claw-free graphs.

preprint2016arXiv

10-tough chordal graphs are Hamiltonian

Chen et al. proved that every 18-tough chordal graph has a Hamilton cycle [Networks 31 (1998), 29-38]. Improving upon their bound, we show that every 10-tough chordal graph is Hamiltonian (in fact, Hamilton-connected). We use Aharoni and Haxell's hypergraph extension of Hall's Theorem as our main tool.

preprint2016arXiv

Nowhere-zero flows in signed graphs: A survey

We survey known results related to nowhere-zero flows and related topics, such as circuit covers and the structure of circuits of signed graphs. We include an overview of several different definitions of signed graph colouring.

preprint2015arXiv

10-Gabriel graphs are Hamiltonian

Given a set $S$ of points in the plane, the $k$ -Gabriel graph of $S$ is the geometric graph with vertex set $S$ , where $p_i,p_j\in S$ are connected by an edge if and only if the closed disk having segment $\bar{p_ip_j}$ as diameter contains at most $k$ points of $S \setminus \{p_i,p_j\}$ . We consider the following question: What is the minimum value of $k$ such that the $k$ -Gabriel graph of every point set $S$ contains a Hamiltonian cycle? For this value, we give an upper bound of 10 and a lower bound of 2. The best previously known values were 15 and 1, respectively.

preprint2014arXiv

Colouring quadrangulations of projective spaces

A graph embedded in a surface with all faces of size 4 is known as a quadrangulation. We extend the definition of quadrangulation to higher dimensions, and prove that any graph G which embeds as a quadrangulation in the real projective space P^n has chromatic number n+2 or higher, unless G is bipartite. For n=2 this was proved by Youngs [J. Graph Theory 21 (1996), 219-227]. The family of quadrangulations of projective spaces includes all complete graphs, all Mycielski graphs, and certain graphs homomorphic to Schrijver graphs. As a corollary, we obtain a new proof of the Lovasz-Kneser theorem.

preprint2014arXiv

Nowhere-zero flows in signed series-parallel graphs

Bouchet conjectured in 1983 that each signed graph that admits a nowhere-zero flow has a nowhere-zero 6-flow. We prove that the conjecture is true for all signed series-parallel graphs. Unlike the unsigned case, the restriction to series-parallel graphs is nontrivial; in fact, the result is tight for infinitely many graphs.

preprint2013arXiv

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs

Hung and Chang showed that for all k>=1 an interval graph has a path cover of size at most k if and only if its scattering number is at most k. They also showed that an interval graph has a Hamilton cycle if and only if its scattering number is at most 0. We complete this characterization by proving that for all k<=-1 an interval graph is -(k+1)-Hamilton-connected if and only if its scattering number is at most k. We also give an O(m+n) time algorithm for computing the scattering number of an interval graph with n vertices an m edges, which improves the O(n^4) time bound of Kratsch, Kloks and Müller. As a consequence of our two results the maximum k for which an interval graph is k-Hamilton-connected can be computed in O(m+n) time.

preprint2013arXiv

Replication in critical graphs and the persistence of monomial ideals

Motivated by questions about square-free monomial ideals in polynomial rings, in 2010 Francisco et al. conjectured that for every positive integer k and every k-critical (i.e., critically k-chromatic) graph, there is a set of vertices whose replication produces a (k+1)-critical graph. (The replication of a set W of vertices of a graph is the operation that adds a copy of each vertex w in W, one at a time, and connects it to w and all its neighbours.) We disprove the conjecture by providing an infinite family of counterexamples. Furthermore, the smallest member of the family answers a question of Herzog and Hibi concerning the depth functions of square-free monomial ideals in polynomial rings, and a related question on the persistence property of such ideals.

preprint2013arXiv

The distance-t chromatic index of graphs

We consider two graph colouring problems in which edges at distance at most $t$ are given distinct colours, for some fixed positive integer $t$ . We obtain two upper bounds for the distance- $t$ chromatic index, the least number of colours necessary for such a colouring. One is a bound of $(2-\eps)Δ^t$ for graphs of maximum degree at most $Δ$ , where $\eps$ is some absolute positive constant independent of $t$ . The other is a bound of $O(Δ^t/\log Δ)$ (as $Δ\to\infty$ ) for graphs of maximum degree at most $Δ$ and girth at least $2t+1$ . The first bound is an analogue of Molloy and Reed's bound on the strong chromatic index. The second bound is tight up to a constant multiplicative factor, as certified by a class of graphs of girth at least $g$ , for every fixed $g \ge 3$ , of arbitrarily large maximum degree $Δ$ , with distance- $t$ chromatic index at least $Ω(Δ^t/\log Δ)$ .

preprint2013arXiv

The fractional chromatic number of triangle-free subcubic graphs

Heckman and Thomas conjectured that the fractional chromatic number of any triangle-free subcubic graph is at most 14/5. Improving on estimates of Hatami and Zhu and of Lu and Peng, we prove that the fractional chromatic number of any triangle-free subcubic graph is at most 32/11 (which is roughly 2.909).

preprint2012arXiv

A short proof of the tree-packing theorem

We give a short elementary proof of Tutte and Nash-Williams' characterization of graphs with k edge-disjoint spanning trees.

preprint2012arXiv

Multiple Petersen subdivisions in permutation graphs

A permutation graph is a cubic graph admitting a 1-factor M whose complement consists of two chordless cycles. Extending results of Ellingham and of Goldwasser and Zhang, we prove that if e is an edge of M such that every 4-cycle containing an edge of M contains e, then e is contained in a subdivision of the Petersen graph of a special type. In particular, if the graph is cyclically 5-edge-connected, then every edge of M is contained in such a subdivision. Our proof is based on a characterization of cographs in terms of twin vertices. We infer a linear lower bound on the number of Petersen subdivisions in a permutation graph with no 4-cycles, and give a construction showing that this lower bound is tight up to a constant factor.

preprint2012arXiv

Star subdivisions and connected even factors in the square of a graph

For any positive integer $s$ , a $[2,2s]$ -factor in a graph $G$ is a connected even factor with maximum degree at most $2s$ . We prove that if every induced $S(K_{1, 2s+1})$ in a graph $G$ has at least 3 edges in a block of degree at most two, then $G^2$ has a $[2,2s]$ -factor. This extends the results of Hendry and Vogler and of Abderrezzak et al.

preprint2011arXiv

Hamilton cycles in 5-connected line graphs

A conjecture of Carsten Thomassen states that every 4-connected line graph is hamiltonian. It is known that the conjecture is true for 7-connected line graphs. We improve this by showing that any 5-connected line graph of minimum degree at least 6 is hamiltonian. The result extends to claw-free graphs and to Hamilton-connectedness.

preprint2011arXiv

The rainbow connection number of 2-connected graphs

The rainbow connection number of a graph G is the least number of colours in a (not necessarily proper) edge-colouring of G such that every two vertices are joined by a path which contains no colour twice. Improving a result of Caro et al., we prove that the rainbow connection number of every 2-connected graph with n vertices is at most the ceiling of n/2. The bound is optimal.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Tomáš Kaiser

Research overview

Is this your work?

19 publications

Graphs of low average degree without independent transversals

Hamilton cycles in line graphs of 3-hypergraphs

Quasigraphs and skeletal partitions

Edge-critical subgraphs of Schrijver graphs

The hamiltonicity of essentially 9-connected line graphs

10-tough chordal graphs are Hamiltonian

Nowhere-zero flows in signed graphs: A survey

10-Gabriel graphs are Hamiltonian

Colouring quadrangulations of projective spaces

Nowhere-zero flows in signed series-parallel graphs

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs

Replication in critical graphs and the persistence of monomial ideals

The distance-t chromatic index of graphs

The fractional chromatic number of triangle-free subcubic graphs

A short proof of the tree-packing theorem

Multiple Petersen subdivisions in permutation graphs

Star subdivisions and connected even factors in the square of a graph

Hamilton cycles in 5-connected line graphs

The rainbow connection number of 2-connected graphs

See the researcher in context

Building this map preview