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
Let Sk(n) be the maximum number of orientations of an n-vertex graph G in which no copy of Kk is strongly connected. For all integers n, k≥4 where n≥5 or k≥5, we prove that Sk(n)=2tk−1(n), where tk−1(n) is the number of edges of the n-vertex (k−1)-partite Turán graph Tk−1(n), and that Tk−1(n) is the only n-vertex graph with this number of orientations. Furthermore, S4(4)=40 and this maximality is achieved only by K4.
Alon and Yuster proved that the number of orientations of any n-vertex graph in which every K3 is transitively oriented is at most 2⌊n2/4⌋ for n≥104 and conjectured that the precise lower bound on n should be n≥8. We confirm their conjecture and, additionally, characterize the extremal families by showing that the balanced complete bipartite graph with n vertices is the only n-vertex graph for which there are exactly 2⌊n2/4⌋ such orientations.
Tuza (1981) conjectured that the size τ(G) of a minimum set of edges that intersects every triangle of a graph G is at most twice the size ν(G) of a maximum set of edge-disjoint triangles of G. In this paper we present three results regarding Tuza's Conjecture. We verify it for graphs with treewidth at most 6; we show that τ(G)≤23ν(G) for every planar triangulation G different from K4; and that τ(G)≤59ν(G)+51 if G is a maximal graph with treewidth 3. Our first result strengthens a result of Tuza, implying that τ(G)≤2ν(G) for every K8-free chordal graph G.
Let χk′(G) denote the minimum number of colors needed to color the edges of a graph G in a way that the subgraph spanned by the edges of each color has all degrees congruent to 1(modk). Scott [{\em Discrete Math. 175}, 1-3 (1997), 289--291] proved that χk′(G)≤5k2logk, and thus settled a question of Pyber [{\em Sets, graphs and numbers} (1992), pp. 583--610], who had asked whether χk′(G) can be bounded solely as a function of k. We prove that χk′(G)=O(k), answering affirmatively a question of Scott.
A T-decomposition of a graph G is a set of edge-disjoint copies of T in G that cover the edge set of G. Graham and Häggkvist (1989) conjectured that any 2ℓ-regular graph G admits a T-decomposition if T is a tree with ℓ edges. Kouider and Lonc (1999) conjectured that, in the special case where T is the path with ℓ edges, G admits a T-decomposition D where every vertex of G is the end-vertex of exactly two paths of D, and proved that this statement holds when G has girth at least (ℓ+3)/2. In this paper we verify Kouider and Lonc's Conjecture for paths of length 4.
We study the Decomposition Conjecture posed by Barát and Thomassen (2006), which states that for every tree T there exists a natural number kT such that, if G is a kT-edge-connected graph and ∣E(T)∣ divides ∣E(G)∣, then G admits a decomposition into copies of T. In a series of papers, Thomassen verified this conjecture for stars, some bistars, paths of length 3, and paths whose length is a power of 2. We verify the Decomposition Conjecture for paths of length 5.
Tibor Gallai conjectured that the edge set of every connected graph G on n vertices can be partitioned into ⌈n/2⌉ paths. Let Gk be the class of all 2k-regular graphs of girth at least 2k−2 that admit a pair of disjoint perfect matchings. In this work, we show that Gallai's conjecture holds in Gk, for every k≥3. Further, we prove that for every graph G in Gk on n vertices, there exists a partition of its edge set into n/2 paths of lengths in {2k−1,2k,2k+1}.
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.