Research work of Adam Kabela

I worked as an assistant professor at the Faculty of Applied Sciences, University of West Bohemia. Before that I was a postdoctoral researcher at the Faculty of Informatics, Masaryk University in the group led by Dan Kráľ, and a researcher and Ph.D. student at the University of West Bohemia, my studies were advised by Tomáš Kaiser.

I am interested in Combinatorics and Graph Theory. The results of my research can be found listed below.

My recent work involves solving Neumann-Lara's conjecture on colouring small oriented graphs, and solving the conjecture of Albert, Atkinson, Handley, Holton and Stromquist on densities of layered permutations. We solved the former with Thomas Bellitto, Nicolas Bousquet and Théo Pierron by proving that every tournament on 18 nodes admits a 4-colouring of nodes such that each colour induces an acyclic graph. We solved the latter with Dan Kráľ, Jon Noel and Théo Pierron by exhibiting layered permutations whose asymptotic density maximisers have an unbounded number of layers.

Research papers

Every 3-connected {K_{1,3}, Γ_3}-free graph is Hamilton-connected

joint work with Mária Skyvová, Zdeněk Ryjáček and Petr Vrána

Discrete Mathematics (2025) | arXiv | code

Abstract

We show that every 3-connected {K_{1,3}, Γ_3}-free graph is Hamilton-connected, where Γ_3 is the graph obtained by joining two vertex-disjoint triangles with a path of length 3. This resolves one of the two last open cases in the characterization of pairs of connected forbidden subgraphs implying Hamilton-connectedness. The proof is based on a new closure technique, developed in a previous paper, and on a structural analysis of small subgraphs, cycles and paths in line graphs of multigraphs. The most technical steps of the analysis are computer-assisted.

A closure for Hamilton-connectedness in {K_{1,3}, Γ_3}-free graphs

joint work with Mária Skyvová, Zdeněk Ryjáček and Petr Vrána

Discrete Mathematics (2024) | arXiv

Abstract

We introduce a closure technique for Hamilton-connectedness of {K_{1,3}, Γ_3}-free graphs, where Γ_3 is the graph obtained by joining two vertex-disjoint triangles with a path of length 3. The closure turns a claw-free graph into a line graph of a multigraph while preserving its (non)-Hamilton-connectedness. The most technical parts of the proof are computer-assisted.

The main application of the closure is given in a subsequent paper showing that every 3-connected {K_{1,3}, Γ_3}-free graph is Hamilton-connected, thus resolving one of the two last open cases in the characterization of pairs of connected forbidden subgraphs implying Hamilton-connectedness.

Improved bounds for the binary paint shop problem

joint work with Jaroslav Hančl, Michal Opler, Jakub Sosnovec, Robert Šámal and Pavel Valtr

Computing and Combinatorics (2024)

Abstract

We improve bounds for the binary paint shop problem posed by Meunier and Neveu (2012). In particular, we disprove their conjectured upper bound for the number of color changes by giving a linear lower bound. We show that the recursive greedy heuristics is not optimal by providing a tiny improvement. We also introduce a new heuristics, recursive star greedy, that a preliminary analysis shows to be 10% better.

The smallest 5-chromatic tournament

joint work with Thomas Bellitto, Nicolas Bousquet and Théo Pierron

Mathematics of Computation (2024) | arXiv | code

Abstract

A coloring of a digraph is a partition of its vertex set such that each class induces a digraph with no directed cycles. A digraph is k-chromatic if k is the minimum number of classes in such partition, and a digraph is oriented if there is at most one arc between each pair of vertices. Clearly, the smallest k-chromatic digraph is the complete digraph on k vertices, but determining the order of the smallest k-chromatic oriented graphs is a challenging problem. It is known that the smallest 2-, 3- and 4-chromatic oriented graphs have 3, 7 and 11 vertices, respectively. In 1994, Neumann-Lara conjectured that a smallest 5-chromatic oriented graph has 17 vertices. We solve this conjecture and show that the correct order is 19.

No additional tournaments are quasirandom-forcing

joint work with Robert Hancock, Dan Kráľ, Taísa Martins, Roberto Parente, Fiona Skerman and Jan Volec

European Journal of Combinatorics (2023) | arXiv | code

Abstract

A tournament H is quasirandom-forcing if the following holds for every sequence (Gn)n∈N of tournaments of growing orders: if the density of H in Gn converges to the expected density of H in a random tournament, then (Gn)n∈N is quasirandom. Every transitive tournament with at least 4 vertices is quasirandom-forcing, and Coregliano et al. (2019) showed that there is also a non-transitive 5-vertex tournament with the property. We show that no additional tournament has this property. This extends the result of Bucic et al. (2021) that the non-transitive tournaments with seven or more vertices do not have this property.

Density maximizers of layered permutations

joint work with Dan Kráľ, Jon Noel and Théo Pierron

Electronic Journal of Combinatorics (2022) | arXiv

Abstract

A permutation is layered if it contains neither 231 nor 312 as a pattern. It is known that, if σ is a layered permutation, then the density of σ in a permutation of order n is maximized by a layered permutation. Albert, Atkinson, Handley, Holton and Stromquist (2002) claimed that the density of a layered permutation with layers of sizes (a, 1, b) where a, b ≥ 2 is asymptotically maximized by layered permutations with a bounded number of layers, and conjectured that the same holds if a layered permutation has no consecutive layers of size one and its first and last layers are of size at least two. We show that, if σ is a layered permutation whose first layer is sufficiently large and second layer is of size one, then the number of layers tends to infinity in every sequence of layered permutations asymptotically maximizing the density of σ. This disproves the conjecture and the claim of Albert et al. We complement this result by giving sufficient conditions on a layered permutation to have asymptotic or exact maximizers with a bounded number of layers.

Forbidden induced pairs for perfectness and ω-colourability of graphs

joint work with Maria Chudnovsky, Binlong Li and Petr Vrána

Electronic Journal of Combinatorics (2022) | arXiv

Abstract

We characterise the pairs of graphs {X, Y} such that all {X, Y}-free graphs (distinct from C5) are perfect. Similarly, we characterise pairs {X, Y} such that all {X, Y}-free graphs (distinct from C5) are ω-colourable (that is, their chromatic number is equal to their clique number). More generally, we show characterizations of pairs {X, Y} for perfectness and ω-colourability of all connected {X, Y}-free graphs which are of independence at least 3, distinct from an odd cycle, and of order at least n0, and similar characterisations subject to each subset of these additional constraints. (The classes are non-hereditary and the characterisations for perfectness and ω-colourability are different.) We build on recent results of Brause et al. on {claw, Y}-free graphs, and we use Ramsey’s Theorem and the Strong Perfect Graph Theorem as main tools. We relate the present characterisations to known results on forbidden pairs for χ-boundedness and deciding k-colourability in polynomial time.

Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4

joint work with Christoph Brause, Trung Duy Doan, Přemysl Holub, Zdeňek Ryjáček, Ingo Schiermeyer and Petr Vrána

Discrete Mathematics (2022) | arXiv

Abstract

For every graph X, we consider the class of all connected {claw, X}-free graphs which are distinct from an odd cycle and have independence number at least 4, and we show that all graphs in the class are perfect if and only if X is an induced subgraph of some of P6, K1 ∪ P5, 2P3, Z2 or K1 ∪ Z1. Furthermore, for X chosen as 2K1 ∪ K3, we list all eight imperfect graphs belonging to the class; and for every other choice of X, we show that there are infinitely many such graphs. In addition, for X chosen as B_{1,2}, we describe the structure of all imperfect graphs in the class.

Packing and covering directed triangles asymptotically

joint work with Jake Cooper, Andrzej Grzesik and Dan Kráľ

European Journal of Combinatorics (2022) | arXiv

Abstract

A well-known conjecture of Tuza asserts that if a graph has at most t pairwise edge-disjoint triangles, then it can be made triangle-free by removing at most 2t edges. If true, the factor 2 would be best possible. In the directed setting, also asked by Tuza, the analogous statement has recently been proven, however, the factor 2 is not optimal. In this paper, we show that if an n-vertex directed graph has at most t pairwise arc-disjoint directed triangles, then there exists a set of at most 1.8t + o(n^2) arcs that meets all directed triangles. We complement our result by presenting two constructions of large directed graphs with t ∈ Ω(n^2) whose smallest such set has 1.5t − o(n^2) arcs.

Trestles in the squares of graphs

joint work with Jakub Teska

Discrete Mathematics (2021) | arXiv

Abstract

We show that the square of every connected S(K_{1,4})-free graph satisfying a matching condition has a 2-connected spanning subgraph of maximum degree at most 3. Furthermore, we characterise trees whose square has a 2-connected spanning subgraph of maximum degree at most k. This generalises the results on S(K_{1,3})-free graphs of Henry and Vogler (1985) and Harary and Schwenk (1971), respectively.

Coloring graphs by translates in the circle

joint work with Pablo Candela, Carlos Catalá, Robert Hancock, Dan Kráľ, Ander Lamaison and Lluís Vena

European Journal of Combinatorics (2021) | arXiv

Abstract

The fractional and circular chromatic numbers are the two most studied non-integral refinements of the chromatic number of a graph. Starting from the definition of a coloring base of a graph, which originated in work related to ergodic theory, we formalize the notion of a gyrocoloring of a graph: the vertices are colored by translates of a single Borel set in the circle group, and neighbouring vertices receive disjoint translates. The corresponding gyrochromatic number of a graph always lies between the fractional chromatic number and the circular chromatic number. We investigate basic properties of gyrocolorings. In particular, we construct examples of graphs whose gyrochromatic number is strictly between the fractional chromatic number and the circular chromatic number. We also establish several equivalent definitions of the gyrochromatic number, including a version involving all finite abelian groups.

On forbidden induced subgraphs for K_{1,3}-free perfect graphs

joint work with Christoph Brause, Přemysl Holub, Zdeňek Ryjáček, Ingo Schiermeyer and Petr Vrána

Discrete Mathematics (2019) | arXiv

Abstract

Considering connected claw-free graphs with independence number at least 3, Chudnovsky and Seymour (2010) showed that every such graph, say G, is 2ω-colourable where ω denotes the clique number of G. We study (claw, Y)-free graphs, and show that the following three statements are equivalent.

(1) Every connected (claw, Y)-free graph which is distinct from an odd cycle and which has independence number at least 3 is perfect.

(2) Every connected (claw, Y)-free graph which is distinct from an odd cycle and which has independence number at least 3 is ω-colourable.

(3) Y is isomorphic to an induced subgraph of P5 or Z2 (where Z2 is also known as hammer).

Long paths and toughness of k-trees and chordal planar graphs

solo work

Discrete Mathematics (2019) | arXiv

Abstract

We show that every k-tree of toughness greater than k/3 is Hamilton-connected for k ≥ 3. (In particular, chordal planar graphs of toughness greater than 1 are Hamilton-connected.) This improves the result of Broersma et al. (2007) and generalizes the result of Böhme et al. (1999). On the other hand, we present graphs whose longest paths are short. Namely, we construct 1-tough chordal planar graphs and 1-tough planar 3-trees, and we show that the shortness exponent of the class is 0, at most log_{30} 22, respectively. Both improve the bound of Böhme et al. Furthermore, the construction provides k-trees (for k ≥ 4) of toughness greater than 1.

Planar graphs have two-coloring number at most 8

joint work with Zdeněk Dvořák and Tomáš Kaiser

Journal of Combinatorial Theory, Series B (2018) | arXiv

Abstract

We prove that the two-coloring number of any planar graph is at most 8. This resolves a question of Kierstead et al. (2009). The result is optimal.

Bounding the distance among longest paths in a connected graph

joint work with Jan Ekstein, Shinya Fujita and Jakub Teska

Discrete Mathematics (2018) | arXiv

Abstract

It is easy to see that in a connected graph any 2 longest paths have a vertex in common. For k ≥ 7, Skupien in 1996 obtained a connected graph in which some k longest paths have no common vertex, but every k − 1 longest paths have a common vertex. It is not known whether every 3 longest paths in a connected graph have a common vertex and similarly for 4, 5, and 6 longest path. Fujita et al. in 2015 give an upper bound on distance among 3 longest paths in a connected graph. In this paper we give a similar upper bound on distance between 4 longest paths and also for k longest paths, in general.

An update on non-Hamiltonian 5/4-tough maximal planar graphs

solo work

Discrete Mathematics (2018) | arXiv

Abstract

Studying the shortness of longest cycles in maximal planar graphs, we improve the upper bound on the shortness exponent of the class of 5/4-tough maximal planar graphs presented by Harant and Owens (1995). In addition, we present two generalizations of a similar result of Tkáč (1996) who considered 1-tough maximal planar graphs; we remark that one of these generalizations gives a tight upper bound. We fix a problematic argument used in the first paper.

10-tough chordal graphs are Hamiltonian

joint work with Tomáš Kaiser

Journal of Combinatorial Theory, Series B (2017) | arXiv

Abstract

Chen et al. (1998) proved that every 18-tough chordal graph has a Hamilton cycle. 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.

Preprints

Packing T-connectors in graphs needs more connectivity

joint work with Roman Čada, Tomáš Kaiser and Petr Vrána

arXiv

Abstract

Strengthening the classical concept of Steiner trees, West and Wu (2012) introduced the notion of a T-connector in a graph G with a set T of terminals. They conjectured that if the set T is 3k-edge-connected in G, then G contains k edge-disjoint T-connectors. We disprove this conjecture by constructing infinitely many counterexamples for k = 1 and for each even k.

The number of abundant elements in union-closed families without small sets

joint work with Michal Polák and Jakub Teska

arXiv

Abstract

We let F be a finite family of sets closed under taking unions and ∅ ∉ F, and call an element abundant if it belongs to more than half of the sets of F. In this notation, the classical Frankl’s conjecture (1979) asserts that F has an abundant element. As possible strengthenings, Poonen (1992) conjectured that if F has precisely one abundant element, then this element belongs to each set of F, and Cui and Hu (2019) investigated whether F has at least k abundant elements if a smallest set of F is of size at least k. Cui and Hu conjectured that this holds for k = 2 and asked whether this also holds for the cases k = 3 and k > n/2 where n is the size of the largest set of F.

We show that F has at least k abundant elements if k ≥ n − 3, and that F has at least k − 1 abundant elements if k = n − 4, and we construct a union-closed family with precisely k − 1 abundant elements for every k and n satisfying n − 4 ≥ k ≥ 3 and n ≥ 9 (and for k = 3 and n = 8). We also note that F always has at least min{n, 2k − n + 1} abundant elements. On the other hand, we construct a union-closed family with precisely two abundant elements for every k and n satisfying n ≥ max{3, 5k − 4}. Lastly, we show that Cui and Hu’s conjecture for k = 2 stands between Frankl’s conjecture and Poonen’s conjecture.

Equivalent formulation of Thomassen's conjecture using Tutte paths in claw-free graphs

joint work with Petr Vrána and Zdeněk Ryjáček

arXiv

Abstract

We continue studying Thomassen’s conjecture (every 4-connected line graph has a Hamilton cycle) in the direction of a recently shown equivalence with Jackson’s conjecture (every 2-connected claw-free graph has a Tutte cycle), and we extend the equivalent formulation as follows: In each connected claw-free graph, every two vertices are connected by a maximal path which is a Tutte path.

Hadwiger meets Cayley

joint work with Jake Cooper, Dan Kráľ and Théo Pierron

arXiv

Abstract

We show that every connected k-chromatic graph contains at least k^(k−2) spanning trees.

Ph.D. Thesis

Toughness and Hamiltonicity of graphs

University of West Bohemia, 2018 | pdf

Abstract

The present thesis is motivated by the study of Chvátal's t_0-tough conjecture. We recall this conjecture in the context of Hamiltonian Graph Theory. We review partial results to the conjecture, and we analyse constructions which provide lower bounds to this conjecture and to similar problems. We discuss some unifying views on the successful approaches towards this conjecture. Following the ideas presented in the thesis, we suggest possible directions for further research.

We present new results related to the t_0-tough conjecture. In particular, we apply the hypergraph extension of Hall's theorem and show that every 10-tough chordal graph is Hamilton-connected. Also we show that k-trees of toughness greater than k/3 are Hamilton-connected for k >= 3 (and consequently, chordal planar graphs of toughness greater than 1 are Hamilton-connected). These results improve the results of Chen et al. (1998), Broersma et al. (2007) and Böhme et al. (1999). In addition, we study so-called multisplit graphs and show that toughness at least 2 implies Hamilton-connectedness of these graphs; and studying certain 'cactus-like' graphs, we show that their Hamiltonicity can be decided by using Max-flow min-cut theorem.

Furthermore, we present constructions of graphs of relatively high toughness whose longest cycles are relatively short. Namely, we construct maximal planar graphs of toughness 5/4, 8/7, greater than 1, respectively; and 1-tough chordal planar graphs, 1-tough planar 3-trees, and k-trees of toughness greater than 1 for k >= 4. These constructions improve the bounds presented by Harant and Owens (1995), Tkáč (1996), Böhme et al. (1999) and Broersma et al. (2007).