Adam Kabela  |  kabela@kma.zcu.cz

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 working with 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

Improved bounds for the binary paint shop problem

joint work with Jaroslav Hančl, Michal Opler (Czech Technical University, Czech Republic), Jakub Sosnovec, Robert Šámal (Charles University, Czech Republic) and Pavel Valtr (Charles University, Czech Republic)

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 (Sorbonne University, France), Nicolas Bousquet (University of Lyon, France) and Théo Pierron (University of Lyon, France)

Mathematics of Computation (2023)  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 (Heidelberg University, Germany), Dan Kráľ (Masaryk University, Czech Republic), Taísa Martins (Fluminense Federal University, Brazil), Roberto Parente (Federal University of Bahia, Brazil), Fiona Skerman (Uppsala University, Sweden) and Jan Volec (Czech Technical University, Czech Republic)

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

with Dan Kráľ (Masaryk University, Czech Republic), Jon Noel (University of Victoria, Canada) and Théo Pierron (University of Lyon, France)

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

with Maria Chudnovsky (Princeton University, U.S.A.), Binlong Li (Northwestern Polytechnical University, China) and Petr Vrána (University of West Bohemia, Czech Republic)

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

with Christoph Brause (Freiberg University of Mining and Technology, Germany), Trung Duy Doan (University of Science and Technology, Vietnam), Přemysl Holub (University of West Bohemia, Czech Republic), Zdeňek Ryjáček (University of West Bohemia, Czech Republic), Ingo Schiermeyer, (Freiberg University of Mining and Technology, Germany) and Petr Vrána (University of West Bohemia, Czech Republic)

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

with Jake Cooper (Masaryk University, Czech Republic), Andrzej Grzesik (Jagiellonian University, Poland) and Dan Kráľ (Masaryk University, Czech Republic)

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

with Jakub Teska (University of West Bohemia, Czech Republic)

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

with Pablo Candela (Autonomous University of Madrid, Spain), Carlos Catalá (Autonomous University of Madrid, Spain), Robert Hancock (Heidelberg University, Germany), Dan Kráľ (Masaryk University, Czech Republic), Ander Lamaison (Masaryk University, Czech Republic) and Lluís Vena (Charles University, Czech Republic)

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

with Christoph Brause (Freiberg University of Mining and Technology, Germany), Přemysl Holub (University of West Bohemia, Czech Republic), Zdeňek Ryjáček (University of West Bohemia, Czech Republic), Ingo Schiermeyer, (Freiberg University of Mining and Technology, Germany) and Petr Vrána (University of West Bohemia, Czech Republic)

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

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

with Zdeněk Dvořák (Charles University, Czech Republic) and Tomáš Kaiser (University of West Bohemia, Czech Republic)

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

with Jan Ekstein (University of West Bohemia, Czech Republic), Shinya Fujita (Yokohama City University, Japan) and Jakub Teska (University of West Bohemia, Czech Republic)

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

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

with Tomáš Kaiser (University of West Bohemia, Czech Republic)

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

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

with Mária Skyvová (University of West Bohemia, Czech Republic), Zdeněk Ryjáček (University of West Bohemia, Czech Republic) and Petr Vrána (University of West Bohemia, Czech Republic)

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

with Mária Skyvová (University of West Bohemia, Czech Republic), Zdeněk Ryjáček (University of West Bohemia, Czech Republic) and Petr Vrána (University of West Bohemia, Czech Republic)

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.

Packing T-connectors in graphs needs more connectivity

with Roman Čada (University of West Bohemia, Czech Republic), Tomáš Kaiser (University of West Bohemia, Czech Republic) and Petr Vrána (University of West Bohemia, Czech Republic)

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

with Michal Polák (University of West Bohemia, Czech Republic) and Jakub Teska (University of West Bohemia, Czech Republic).

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

with Petr Vrána (University of West Bohemia, Czech Republic)

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

with Jake Cooper (Masaryk University, Czech Republic), Dan Kráľ (Masaryk University, Czech Republic) and Théo Pierron (Masaryk University, Czech Republic) 

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).

Talks at math events

Forbidden induced pairs and additional constraints for perfectness and ω-colourability of graphs

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

6th Xi'an International Workshop on Graph Theory and Combinatorics, online, 2022  |  slides 

An introduction to induced-saturated graphs

based on joint work with Pavel Dvořák, Tomáš Kaiser, Michal Opler, Théo Pierron and Aneta Pokorná

STIGMA, Czech Republic, 2021

Layered permutations and their density maximisers

based on joint work with Dan Král', Jon Noel and Théo Pierron

Permutation Patterns, online, 2021 |  slides 

Disproving a conjecture on layered permutation density maximisers 

based on joint work with Dan Král', Jon Noel and Théo Pierron

seminar of the G²OAT research group, online, 2021

Disproving a conjecture on layered permutation density maximisers

based on joint work with Dan Král', Jon Noel and Théo Pierron

55th Czech-Slovak Conference on Graph Theory, Czech Republic, 2020

Quasirandom-forcing tournaments

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

Seminar series on Graph Theory at Comenius University, Slovakia, 2019

Forbidden pairs and perfect graphs

based on joint work with Petr Vrána

Midsummer Combinatorial Workshop XXIV, Czech Republic, 2019

Forbidden pairs and perfect graphs

based on joint work with Petr Vrána

Ghent Graph Theory Workshop, Belgium, 2019

Tough enough H-graphs are Hamiltonian

based on joint work with Tomáš Kaiser

54th Czech-Slovak Conference Graphs, Slovakia, 2019

Equivalent formulation of Thomassen's conjecture using Tutte paths in K_{1,3}-free graphs

based on joint work with Petr Vrána

10th Workshop on the Matthews-Sumner Conjecture and Related Problems, Czech Republic, 2019  |  slides

Toughness and Hamiltonicity and using duality theorems

including joint work with Tomáš Kaiser and Hajo Broersma

Algorithms seminar series at University of Bergen, Norway, 2018  |  slides (pictures animate on click, download and open, I used Adobe Acrobat)

Spanning a tough graph

including joint work with Tomáš Kaiser and Hajo Broersma

Bucharest Graph Theory Workshop, Romania, 2018

Bounding shortness exponent of tough maximal planar graphs

52nd Czech-Slovak Conference on Combinatorics and Graph Theory, Czech Republic, 2017

Toughness and Hamiltonicity for special graph classes

based on joint work with Hajo Broersma, Hao Qi and Elkin Vumar

Bordeaux Graph Workshop, France, 2016

10-tough chordal graphs are Hamiltonian

based on joint work with Tomáš Kaiser

51th Czech-Slovak Conference Grafy, Slovakia, 2016  |  slides (experimental slides, download and open)

Poster

Smallest 5-chromatic tournament

based on joint work with Thomas Bellitto (Sorbonne University, France), Nicolas Bousquet (University of Lyon, France) and Théo Pierron (University of Lyon, France)

DIMEA Days, Czech Republic, 2022