Search

Let fk(n,H) denote the maximum number of edges not contained in any monochromatic copy of H in a k-coloring of the edges of Kn, and let ex(n,H) denote the Tur\'an number of H. In place of f2(n,H) we simply write f(n,H). Keevash and Sudakov proved that f(n,H) = ex(n,H) if H is an edge-critical graph or C4 and asked if this equality holds for any graph H. All known exact values of this question require H to contain at least one cycle. In this paper we focus on acyclic graphs and present the following results: (1) We prove f(n,H) = ex(n,H) when H is a spider or a double broom. (2) We show that a tail in H is a path P3 = v0v1v2 such that v2 is only adjacent to v1, and v1 is only adjacent to v0, v2 in H. We obtain a tight upper bound for f(n,H) when H is a bipartite graph with a tail. This result provides the first bipartite graphs which answer the question of Keevash and Sudakov in the negative. (3) We answer a question of Liu, Pikhurko, and Sharifzadeh who asked if fk(n,T) =(k 1)ex(n,T) when T is a tree. We provide an upper bound for f2k(n,P2k) and show it is tight when 2k 1 is prime. This provides a negative answer to their question. [ABSTRACT FROM AUTHOR]

An odd (resp. even) subgraph in a multigraph is its subgraph in which every vertex has odd (resp. even) degree. We say that a multigraph can be decomposed into two odd subgraphs if its edge set can be partitioned into two sets so that both form odd subgraphs. In this paper we give a necessary and sufficient condition for thedecomposability of a multigraph into two odd subgraphs. We also present a polynomial time algorithm for finding such a decomposition or showing its non-existence. We also deal with the case of the decomposability into an even subgraph and an odd subgraph. [ABSTRACT FROM AUTHOR]