Search

We show that for every ℓ , there exists d ℓ such that every 3-edge-connected graph with minimum degree d ℓ can be edge-partitioned into paths of length ℓ (provided that its number of edges is divisible by ℓ). This improves a result asserting that 24-edge-connectivity and high minimum degree provides such a partition. This is best possible as 3-edge-connectivity cannot be replaced by 2-edge connectivity. [ABSTRACT FROM AUTHOR]

Abstract: We prove a general result concerning cyclic orderings of the elements of a matroid. For each matroid M, weight function , and positive integer D, the following are equivalent. (1) For all , we have . (2) There is a map ϕ that assigns to each element e of a set of cyclically consecutive elements in the cycle so that each set , for , is independent. As a first corollary we obtain the following. For each matroid M such that and are coprime, the following are equivalent. (1) For all non-empty , we have . (2) There is a cyclic permutation of in which all sets of cyclically consecutive elements are bases of M. A second corollary is that the circular arboricity of a matroid is equal to its fractional arboricity. These results generalise classical results of Edmonds, Nash-Williams and Tutte on covering and packing matroids by bases and graphs by spanning trees. [Copyright &y& Elsevier]

Abstract: We prove that every graph G has a vertex partition into a cycle and an anticycle (a cycle in the complement of G). Emptyset, singletons and edges are considered as cycles. This problem was posed by Lehel and shown to be true for very large graphs by Łuczak, Rödl and Szemerédi [T. Łuczak, V. Rödl, E. Szemerédi, Partitioning two-colored complete graphs into two monochromatic cycles, Combin. Probab. Comput. 7 (1998) 423–436], and more recently for large graphs by Allen [P. Allen, Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles, Combin. Probab. Comput. 17 (2008) 471–486]. [Copyright &y& Elsevier]

Answering a question of Adrian Bondy (Per. Comm.), we prove that every strong digraph has a spanning strong subgraph with at most n+2α−2 arcs, where α is the size of a maximum stable set of D. Such a spanning subgraph can be found in polynomial time. An infinite family of oriented graphs for which this bound is sharp was given by Odile Favaron (Discrete Math. 146 (1995) 289). A direct corollary of our result is that there exists 2α−1 directed cycles which span D. Tibor Gallai (Theory of Graphs and its Applications, Czech. Acad. Sci. Prague, 1964, p. 161) conjectured that α directed cycles would be enough. [Copyright &y& Elsevier]

A graph is O k -free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite graphs as subgraphs) O k -free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is optimal, as there is an infinite family of O 2 -free graphs without K 2 , 3 as a subgraph and whose treewidth is (at least) logarithmic. Using our result, we show that Maximum Independent Set and 3-Coloring in O k -free graphs can be solved in quasi-polynomial time. Other consequences include that most of the central NP-complete problems (such as Maximum Independent Set , Minimum Vertex Cover , Minimum Dominating Set , Minimum Coloring) can be solved in polynomial time in sparse O k -free graphs, and that deciding the O k -freeness of sparse graphs is polynomial time solvable. [ABSTRACT FROM AUTHOR]

A graph G is called normal if there exist two coverings, C and S of its vertex set such that every member of C induces a clique in G , every member of S induces an independent set in G and C ∩ S ≠ ∅ for every C ∈ C and S ∈ S. It has been conjectured by De Simone and Körner in 1999 that a graph G is normal if G does not contain C 5 , C 7 and C 7 ‾ as an induced subgraph. We disprove this conjecture. [ABSTRACT FROM AUTHOR]

The chromatic number of a directed graph D is the minimum number of colors needed to color the vertices of D such that each color class of D induces an acyclic subdigraph. Thus, the chromatic number of a tournament T is the minimum number of transitive subtournaments which cover the vertex set of T. We show in this note that tournaments are significantly simpler than graphs with respect to coloring. Indeed, while undirected graphs can be altogether "locally simple" (every neighborhood is a stable set) and have large chromatic number, we show that locally simple tournaments are indeed simple. In particular, there is a function f such that if the out-neighborhood of every vertex in a tournament T has chromatic number at most c , then T has chromatic number at most f (c). This answers a question of Berger et al. [ABSTRACT FROM AUTHOR]

A very nice result of Bárány and Lehel asserts that every finite subset X or R d can be covered by h (d) X -boxes (i.e. each box has two antipodal points in X). As shown by Gyárfás and Pálvőlgyi this result would follow from the following conjecture: If a tournament admits a partition of its arc set into k quasi-orders, then its domination number is bounded in terms of k. This question is in turn implied by the Erdős–Sands–Sauer–Woodrow conjecture: If the arcs of a tournament T are coloured with k colour's, there is a set X of at most g (k) vertices such that for every vertex v of T , there is a monochromatic path from X to v. We give a short proof of this statement. We moreover show that the general Sands–Sauer–Woodrow conjecture (which as a special case implies the stable marriage theorem) is valid for directed graphs with bounded stability number. This conjecture remains however open. [ABSTRACT FROM AUTHOR]

We develop a technique, that we call conflict packing , to obtain (and improve) polynomial kernels for several well-studied editing problems. We first illustrate our technique on Feedback Arc Set in Tournaments ( k -FAST ) yielding an alternative and simple proof of a linear kernel for this problem. The technique is then applied to obtain the first linear kernel for the Dense Rooted Triplet Inconsistency ( k -dense-RTI ) problem. A linear kernel for Betweenness in Tournaments ( k -BIT ) is also proved. All these problems share common features. First, they can be expressed as modification problems on a dense set of constant-arity constraints. Also the consistency of the set of constraints can be characterized by means of a bounded size obstructions. The conflict packing technique basically consists of computing a maximal set of small obstructions allowing us either to bound the size of the input or to reduce the input. [ABSTRACT FROM AUTHOR]

We prove that there exist perfect graphs of arbitrarily large clique-chromatic number. These graphs can be obtained from cobipartite graphs by repeatedly gluing along cliques. This negatively answers a question raised by Duffus et al. (1991) [5] . [ABSTRACT FROM AUTHOR]

Abstract: Let denote the maximum number of edge-disjoint triangles in a graph and denote the minimum total weight of a fractional covering of its triangles by edges. Krivelevich proved that for every graph . This is sharp, since for the complete graph we have and . We refine this result by showing that if a graph has , then contains edge-disjoint -subgraphs plus an additional edge-disjoint triangles. Note that just these ’s and triangles witness that . Our proof also yields that for each -free graph . In contrast, we show that for each , there exists a -free graph such that . [Copyright &y& Elsevier]

Abstract: In a recent paper, Amini et al. introduced a general framework to prove duality theorems between tree-decompositions and their dual combinatorial object. They unify all known ad hoc proofs in one duality theorem based on submodular partition functions. This general theorem remains however a bit technical and relies on this particular submodularity property. Instead of partition functions, we propose here a simple combinatorial property of a set of partitions which also gives these duality results. Our approach is both simpler, and a little bit more general. [Copyright &y& Elsevier]

We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs. [ABSTRACT FROM AUTHOR]

A hereditary class of graphs G is χ-bounded if there exists a function f such that every graph G ∈ G satisfies χ (G) ⩽ f (ω (G)) , where χ (G) and ω (G) are the chromatic number and the clique number of G , respectively. As one of the first results about χ -bounded classes, Gyárfás proved in 1985 that if G is P t -free, i.e., does not contain a t -vertex path as an induced subgraph, then χ (G) ⩽ (t − 1) ω (G) − 1. In 2017, Chudnovsky, Scott, and Seymour proved that C ⩾ t -free graphs, i.e., graphs that exclude induced cycles with at least t vertices, are χ -bounded as well, and the obtained bound is again superpolynomial in the clique number. Note that P t − 1 -free graphs are in particular C ⩾ t -free. It remains a major open problem in the area whether for C ⩾ t -free, or at least P t -free graphs G , the value of χ (G) can be bounded from above by a polynomial function of ω (G). We consider a relaxation of this problem, where we compare the chromatic number with the size of a largest balanced biclique contained in the graph as a (not necessarily induced) subgraph. We show that for every t there exists a constant c such that for every ℓ and every C ⩾ t -free graph which does not contain K ℓ , ℓ as a subgraph, it holds that χ (G) ⩽ ℓ c. [ABSTRACT FROM AUTHOR]

It takes n 2 / 4 cliques to cover all the edges of a complete bipartite graph K n / 2 , n / 2 , but how many cliques does it take to cover all the edges of a graph G if G has no K t , t induced subgraph? We prove that O (n 2 − 1 / (2 t) ) cliques suffice for every n -vertex graph; and also prove that, even for graphs with no stable set of size four, we may need more than linearly many cliques. This settles two questions discussed at a recent conference in Lyon. [ABSTRACT FROM AUTHOR]

We investigate the following conjecture of Hehui Wu: for every tournament S , the class of S -free tournaments has bounded domination number. We show that the conjecture is false in general, but true when S is 2-colourable (that is, its vertex set can be partitioned into two transitive sets); the latter follows by a direct application of VC-dimension. Our goal is to go beyond this; we give a non-2-colourable tournament S that satisfies the conjecture. The key ingredient here (perhaps more interesting than the result itself) is that we overcome the unboundedness of the VC-dimension by showing that the set of shattered sets is sparse. [ABSTRACT FROM AUTHOR]

The Barát–Thomassen conjecture asserts that for every tree T on m edges, there exists a constant k T such that every k T -edge-connected graph with size divisible by m can be edge-decomposed into copies of T . So far this conjecture has only been verified when T is a path or when T has diameter at most 4. Here we prove the full statement of the conjecture. [ABSTRACT FROM AUTHOR]

Abstract: We present a polynomial time algorithm that for any graph G and integer , either finds a spanning tree with at least k internal vertices, or outputs a new graph on at most 3k vertices and an integer such that G has a spanning tree with at least k internal vertices if and only if has a spanning tree with at least internal vertices. In other words, we show that the Maximum Internal Spanning Tree problem parameterized by the number of internal vertices k has a 3k-vertex kernel. Our result is based on an innovative application of a classical min–max result about hypertrees in hypergraphs which states that “a hypergraph H contains a hypertree if and only if H is partition-connected.” [Copyright &y& Elsevier]

Abstract: A tournament is a complete graph with its edges directed, and colouring a tournament means partitioning its vertex set into transitive subtournaments. For some tournaments H there exists c such that every tournament not containing H as a subtournament has chromatic number at most c (we call such a tournament H a hero); for instance, all tournaments with at most four vertices are heroes. In this paper we explicitly describe all heroes. [Copyright &y& Elsevier]

Abstract: A tournament is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Feedback Arc Set problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The Feedback Arc Set problem restricted to tournaments is known as the k-Feedback Arc Set in Tournaments (k-FAST) problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance on vertices. In fact, given any fixed , the kernelized instance has at most vertices. Our result improves the previous known bound of on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST. [Copyright &y& Elsevier]

Abstract: Dimitri Grigoriev has shown that for any family of N vectors in the d-dimensional linear space , there exists a vector in E which is orthogonal to at least and at most vectors of the family. We show that the range can be replaced by the much smaller range and we give an efficient, deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated. [Copyright &y& Elsevier]

A relational structure A satisfies the P(n, k) property if whenever the vertex set of A is partitioned into n nonempty parts, the substructure induced by the union of somek of the parts is isomorphic to A. The P(2, 1) property is just the pigeonhole property, (P), introduced by Cameron, and studied by Bonato, Delic´ and Cameron. We classify the countable graphs, tournaments, and oriented graphs with the P(3, 2) property. [Copyright &y& Elsevier]