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.

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. 

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.

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.

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.

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.

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.

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.

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.

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.

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.

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