Partitioning edge-coloured complete graphs into monochromatic cycles

A conjecture of Erdös, Gyárfás, and Pyber says that in any edge-colouring of a complete graph with r colours, it is possible to cover all the vertices with r vertex-disjoint monochromatic cycles. So far, this conjecture has been proven only for $r=2$. In this note we show that in fact this conjecture is false for all $r⩾3$. We also discuss some weakenings of this conjecture which may still be true.     

Partitioning complete graphs by heterochromatic trees

A heterochromatic tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by t _r (G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we determine the heterochromatic tree partition number of r-edge-colored complete graphs. We also find at most t _r (K _n ) vertex-disjoint heterochromatic trees to cover all the vertices in polynomial time for a given r-edge-coloring of K _n .     

Decompositions of edge-coloured infinite complete graphs into monochromatic paths II

We prove that given an edge colouring of an infinite complete graph with finitely many colours, one can partition the vertices of the graph into disjoint monochromatic paths of different colours. This answers a question of R. Rado from 1978.     

Counting shellings of complete bipartite graphs and trees

Journal of Algebraic Combinatorics - A shelling of a graph, viewed as an abstract simplicial complex that is pure of dimension 1, is an ordering of its edges such that every edge is adjacent to...     

Some arrowing results for trees versus complete graphs

For an arbitrary tree T of order m and an arbitrary positive integer n, Chvátal proved that the Ramsey number r(T, K_n) = 1 + (m ? 1) (n ? 1). for graphs G, G₁, and G₂, we say that G arrows G₁ and G₂, written G → (G₁, G₂), if for every factorization G = R ⊕ B, either G₁ is a subgraph of R or G₂ is a subgraph of B. it is shown that (i) for each l ≥ 2, K₁+ (m?1)(n?1) ?E(K₁) → (T, K_n) for m ≥ 2/ ? 1 and n ≥ 2; (ii) K₁ +,(m ?1)(n ?1) ? E(H) → (T, K_n), where H is any tree of order m ? 1, m ≥ 3 and n ≥ 2. It is further shown that result (i) is sharp with respect to the inequality m ≥ 2/? 1; in particular, examples are given to show that K1 + (2l?3)(n?1) E(K₁) ? (P_21?2, K_n) for all n ≥ 2, where P_21?2 denotes the path of order 21 ? 2. Also result (ii) is sharp with respect to the order of H; examples aregiven to show that K₁ + _(m?1)(n?1)? E(K(1, m ? 1)) ?(T, K_n)for any tree T of order m and any n ≥ 2.     

Note on 2-edge-colorings of complete graphs with small monochromatic k-connected subgraphs

Bollob′as and Gy′arf′as conjectured that for n4(k-1) every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n-2k+2 verticesLiu, et alproved that the conjecture holds when n≥13k-15In this note, we characterize all the2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n-2k+2 vertices for n≥13k-15.     

Non-crossing monotone paths and binary trees in edge-ordered complete geometric graphs

Acta Mathematica Hungarica - This paper is devoted to the studying of the weak Orlicz–Lorentz space $$Lambda_X^{varphi, infty}(w)$$ , which can be regarded as an extension of weak Orlicz...     

On the number of rainbow spanning trees in edge-colored complete graphs

A spanning tree of a properly edge-colored complete graph, $K_n$, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if $K_{2m}$ is properly $(2m?1)$-edge-colored, then the edges of $K_{2m}$ can be partitioned into $m$ rainbow spanning trees except when $m=2$. By means of an explicit, constructive approach, in this paper we construct $?\sqrt{6m+9}∕3?$ mutually edge-disjoint rainbow spanning trees for any positive value of $m$. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees.     

Independent trees in graphs

IfG is a finite undirected graph ands is a vertex ofG, then two spanning treesT ₁ andT ₂ inG are calleds — independent if for each vertexx inG the paths fromx tos inT ₁ andT ₂ are openly disjoint. It is known that the following statement is true fork3: IfG isk-connected, then there arek pairwises — independent spanning, trees inG. As a main result we show that this statement is also true fork=4 if we restrict ourselves to planar graphs. Moreover we consider similar statements for weaklys — independent spanning trees (i.e., the tree paths from a vertex tos are edge disjoint) and for directed graphs.     

Vertex partitions of non-complete graphs into connected monochromatic k-regular graphs

In a landmark paper, Erd?s et al. (1991) [3] proved that if $G$ is a complete graph whose edges are colored with $r$ colors then the vertex set of $G$ can be partitioned into at most $c{r}^{2}logr$ monochromatic, vertex disjoint cycles for some constant $c$. Sárközy extended this result to non-complete graphs, and Sárközy and Selkow extended it to $k$-regular subgraphs. Generalizing these two results, we show that if $G$ is a graph with independence number $\alpha \left(G\right)=\alpha$ whose edges are colored with $r$ colors then the vertex set of $G$ can be partitioned into at most ${\left(\alpha r\right)}^{c(\alpha rlog\left(\alpha r\right)+k)}$ vertex disjoint connected monochromatic$k$-regular subgraphs of $G$ for some constant $c$.     

Partitioning edge-coloured complete symmetric digraphs into monochromatic complete subgraphs

Let ${\overrightarrow{K}}_{\mathbb{N}}$ be the complete symmetric digraph on the positive integers. Answering a question of DeBiasio and McKenney, we construct a 2-colouring of the edges of ${\overrightarrow{K}}_{\mathbb{N}}$ in which every monochromatic path has density 0.However, if we restrict the length of monochromatic paths in one colour, then no example as above can exist: We show that every $(r+1)$-edge-coloured complete symmetric digraph (of arbitrary infinite cardinality) containing no directed paths of edge-length ${?}_i$ for any colour $i\le r$ can be covered by ${\prod }_{i\in \left[r\right]}{?}_i$ pairwise disjoint monochromatic complete symmetric digraphs in colour $r+1$.Furthermore, we present a stability version for the countable case of the latter result: We prove that the edge-colouring is uniquely determined on a large subgraph, as soon as the upper density of monochromatic paths in colour $r+1$ is bounded by ${\prod }_{i\in \left[r\right]}\frac{1}{{?}_i}$.     

2-List-coloring planar graphs without monochromatic triangles

We prove that, for every list-assignment of two colors to every vertex of any planar graph, there is a list-coloring such that there is no monochromatic triangle. This proves and extends a conjecture of B. Mohar and R. ?krekovski and a related conjecture of A. Kündgen and R. Ramamurthi.     

Embedding of two-colored right-angled Coxeter groups into products of two binary trees

We prove that every finitely generated 2-colored right-angled Coxeter group Γ can be quasi-isometrically embedded into the product of two binary trees. Moreover we show that the natural extension of this embedding to n-colored groups is not for every group quasi-isometric. Partially supported by Swiss National Science Foundation.