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
We prove that for all natural numbers m and k where k is odd, there exists a natural number N(k) such that any 3-connected cubic graph with at least N(k) vertices contains a cycle of length m modulo k. We also construct a family of graphs showing that this is not true for 2-connected cubic graphs if m and k are divisible by 3 and k≥12.
The Barát-Thomassen conjecture asserts that for every tree T on m edges, there exists a constant kT such that every kT-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.
We introduce the notion of \emph{bounded diameter arboricity}. Specifically, the \emph{diameter-d arboricity} of a graph is the minimum number k such that the edges of the graph can be partitioned into k forests each of whose components has diameter at most d. A class of graphs has bounded diameter arboricity k if there exists a natural number d such that every graph in the class has diameter-d arboricity at most k. We conjecture that the class of graphs with arboricity at most k has bounded diameter arboricity at most k+1. We prove this conjecture for k∈{2,3} by proving the stronger assertion that the union of a forest and a star forest can be partitioned into two forests of diameter at most 18. We use these results to characterize the bounded diameter arboricity for planar graphs of girth at least g for all g=5. As an application we show that every 6-edge-connected planar (multi)graph contains two edge-disjoint 1918-thin spanning trees.
A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index χirr′(G) of a graph G is the smallest number of locally irregular subgraphs needed to edge-decompose G. Not all graphs have such a decomposition, but Baudon, Bensmail, Przybyło, and Woźniak conjectured that if G can be decomposed into locally irregular subgraphs, then χirr′(G)≤3. In support of this conjecture, Przybyło showed that χirr′(G)≤3 holds whenever G has minimum degree at least 1010. Here we prove that every bipartite graph G which is not an odd length path satisfies χirr′(G)≤10. This is the first general constant upper bound on the irregular chromatic index of bipartite graphs. Combining this result with Przybyło's result, we show that χirr′(G)≤328 for every graph G which admits a decomposition into locally irregular subgraphs. Finally, we show that χirr′(G)≤2 for every 16-edge-connected bipartite graph G.
The Tree Decomposition Conjecture by Barát and Thomassen states that for every tree T there exists a natural number k(T) such that the following holds: If G is a k(T)-edge-connected simple graph with size divisible by the size of T, then G can be edge-decomposed into subgraphs isomorphic to T. So far this conjecture has only been verified for paths, stars, and a family of bistars. We prove a weaker version of the Tree Decomposition Conjecture, where we require the subgraphs in the decomposition to be isomorphic to graphs that can be obtained from T by vertex-identifications. We call such a subgraph a homomorphic copy of T. This implies the Tree Decomposition Conjecture under the additional constraint that the girth of G is greater than the diameter of T. As an application, we verify the Tree Decomposition Conjecture for all trees of diameter at most 4.
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.