BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
In this paper and a companion paper, we prove that, if m is sufficiently large, every graph on m+1 vertices that has a universal vertex and minimum degree at least ⌊32m⌋ contains each tree T with m edges as a subgraph. Our result confirms, for large m, an important special case of a recent conjecture by Havet, Reed, Stein, and Wood. The present paper already contains an approximate version of the result.
We prove that, if m is sufficiently large, every graph on m+1 vertices that has a universal vertex and minimum degree at least ⌊32m⌋ contains each tree T with m edges as a subgraph. Our result confirms, for large m, an important special case of a conjecture by Havet, Reed, Stein, and Wood. The present paper builds on the results of a companion paper in which we proved the statement for all trees having a vertex that is adjacent to many leaves.
For any odd t≥9, we present a polynomial-time algorithm that solves the 3-colouring problem, and finds a 3-colouring if one exists, in Pt-free graphs of odd girth at least t−2. In particular, our algorithm works for (P9,C3,C5)-free graphs, thus making progress towards determining the complexity of 3-colouring in Pt-free graphs, which is open for t≥8.
We propose the following conjecture: For every fixed α∈[0,31), each graph of minimum degree at least (1+α)2k and maximum degree at least 2(1−α)k contains each tree with k edges as a subgraph. Our main result is an approximate version of the conjecture for bounded degree trees and large dense host graphs. We also show that our conjecture is asymptotically best possible. The proof of the approximate result relies on a second result, which we believe to be interesting on its own. Namely, we can embed any bounded degree tree into host graphs of minimum/maximum degree asymptotically exceeding 2k and 34k, respectively, as long as the host graph avoids a specific structure.
We prove the Erd\H os--Sós conjecture for trees with bounded maximum degree and large dense host graphs. As a corollary, we obtain an upper bound on the multicolour Ramsey number of large trees whose maximum degree is bounded by a constant.
We survey results and open problems relating degree conditions with tree containment in graphs, random graphs, digraphs and hypergraphs, and their applications in Ramsey theory.
We show that for any colouring of the edges of the complete bipartite graph Kn,n with 3 colours there are 5 disjoint monochromatic cycles which together cover all but o(n) of the vertices. In the same situation, 18 disjoint monochromatic cycles together cover all vertices.
It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable graph without an induced path on t vertices, computes a coloring with max{5,2⌈2t−1⌉−2} many colors. If the input graph is triangle-free, we only need max{4,⌈2t−1⌉+1} many colors. The running time of our algorithm is O((3t−2+t2)m+n) if the input graph has n vertices and m edges.
We show that for any 2-local colouring of the edges of the balanced complete bipartite graph Kn,n, its vertices can be covered with at most~3 disjoint monochromatic paths. And, we can cover almost all vertices of any complete or balanced complete bipartite r-locally coloured graph with O(r2) disjoint monochromatic cycles.\\ We also determine the 2-local bipartite Ramsey number of a path almost exactly: Every 2-local colouring of the edges of Kn,n contains a monochromatic path on n vertices.
A set of vertices X of a graph G is convex if it contains all vertices on shortest paths between vertices of X. We prove that for fixed p, all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time.
An edge colouring of a graph is said to be an r-local colouring if the edges incident to any vertex are coloured with at most r colours. Generalising a result of Bessy and Thomassé, we prove that the vertex set of any 2-locally coloured complete graph may be partitioned into two disjoint monochromatic cycles of different colours. Moreover, for any natural number r, we show that the vertex set of any r-locally coloured complete graph may be partitioned into O(r2logr) disjoint monochromatic cycles. This generalises a result of Erdős, Gyárfás and Pyber.
We prove the following version of the Loebl-Komlos-Sos Conjecture: For every alpha>0 there exists a number M such that for every k>M every n-vertex graph G with at least (0.5+alpha)n vertices of degree at least (1+alpha)k contains each tree T of order k as a subgraph. The method to prove our result follows a strategy common to approaches which employ the Szemeredi Regularity Lemma: we decompose the graph G, find a suitable combinatorial structure inside the decomposition, and then embed the tree T into G using this structure. However, the decomposition given by the Regularity Lemma is not of help when G is sparse. To surmount this shortcoming we use a more general decomposition technique: each graph can be decomposed into vertices of huge degree, regular pairs (in the sense of the Regularity Lemma), and two other objects each exhibiting certain expansion properties.
Considering systems of separations in a graph that separate every pair of a given set of vertex sets that are themselves not separated by these separations, we determine conditions under which such a separation system contains a nested subsystem that still separates those sets and is invariant under the automorphisms of the graph. As an application, we show that the k-blocks -- the maximal vertex sets that cannot be separated by at most k vertices -- of a graph G live in distinct parts of a suitable tree-decomposition of G of adhesion at most k, whose decomposition tree is invariant under the automorphisms of G. This extends recent work of Dunwoody and Krön and, like theirs, generalizes a similar theorem of Tutte for k=2. Under mild additional assumptions, which are necessary, our decompositions can be combined into one overall tree-decomposition that distinguishes, for all k simultaneously, all the k-blocks of a finite graph.
We show that any complete k-partite graph G on n vertices, with k≥3, whose edges are two-coloured, can be covered with two vertex-disjoint monochromatic paths of distinct colours. We prove this under the necessary assumption that the largest partition class of G contains at most n/2 vertices. This extends known results for complete and complete bipartite graphs. Secondly, we show that in the same situation, all but o(n) vertices of the graph can be covered with two vertex-disjoint monochromatic cycles of distinct colours, if colourings close to a split colouring are excluded. From this we derive that the whole graph, if large enough, may be covered with 14 vertex-disjoint monochromatic cycles.
We prove that the list chromatic index of a graph of maximum degree Δ and treewidth ≤2Δ−3 is Δ; and that the total chromatic number of a graph of maximum degree Δ and treewidth ≤Δ/3+1 is Δ+1. This improves results by Meeks and Scott.
We prove that every minimal brick on n vertices has at least n/9 vertices of degree at most 4.
Given a vertex-weighted tree T, the split of an edge xy in T is min{s_x(xy), s_y(xy)} where s_u(uv) is the sum of all weights of vertices that are closer to u than to v in T. Given a set of weighted vertices V and a multiset of splits S, we consider the problem of constructing a tree on V whose splits correspond to S. The problem is known to be NP-complete, even when all vertices have unit weight and the maximum vertex degree of T is required to be no more than 4. We show that the problem is strongly NP-complete when T is required to be a path, the problem is NP-complete when all vertices have unit weight and the maximum degree of T is required to be no more than 3, and it remains NP-complete when all vertices have unit weight and T is required to be a caterpillar with unbounded hair length and maximum degree at most 3. We also design polynomial time algorithms for the variant where T is required to be a path and the number of distinct vertex weights is constant, and the variant where all vertices have unit weight and T has a constant number of leaves. The latter algorithm is not only polynomial when the number of leaves, k, is a constant, but also fixed-parameter tractable when parameterized by k. Finally, we shortly discuss the problem when the vertex weights are not given but can be freely chosen by an algorithm. The considered problem is related to building libraries of chemical compounds used for drug design and discovery. In these inverse problems, the goal is to generate chemical compounds having desired structural properties, as there is a strong correlation between structural properties, such as the Wiener index, which is closely connected to the considered problem, and biological activity.
Bounds on the minimum degree and on the number of vertices at- taining it have been much studied for finite edge-/vertex-minimally k- connected/k-edge-connected graphs. We give an overview of the results known for finite graphs, and show that most of these carry over to infinite graphs if we consider ends of small degree as well as vertices.
We survey various aspects of infinite extremal graph theory and prove several new results. The lead role play the parameters connectivity and degree. This includes the end degree. Many open problems are suggested.
It is well-known that in finite graphs, large complete minors/topological minors can be forced by assuming a large average degree. Our aim is to extend this fact to infinite graphs. For this, we generalise the notion of the relative end degree, which had been previously introduced by the first author for locally finite graphs, and show that large minimum relative degree at the ends and large minimum degree at the vertices imply the existence of large complete (topological) minors in infinite graphs with countably many ends.
The determination of the stability of the long-lived consensus problem is a fundamental open problem in distributed systems. We concentrate on the memoryless binary case with geodesic paths. We offer a conjecture on the stability in this case, exhibit two classes of colourings which attain this conjectured bound, and improve the known lower bounds for all colourings. We also introduce a related parameter, which measures the stability only for certain geodesics, and for which we also prove lower bounds.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.