Search

We determine the 2-color Ramsey number of a connected triangle matching [ABSTRACT FROM AUTHOR]

Abstract: An edge coloring of a tournament T with colors is called k-transitive if the digraph defined by the edges of color i is transitively oriented for each . We explore a conjecture of the second author: For each positive integer k there exists a (least) such that every k-transitive tournament has a dominating set of at most vertices. We show how this conjecture relates to other conjectures and results. For example, it is a special case of a well-known conjecture of Erdős, Sands, Sauer and Woodrow [14] (so the conjecture is interesting even if false). We show that the conjecture implies a stronger conjecture, a possible extension of a result of Bárány and Lehel on covering point sets by boxes. The principle used leads also to an upper bound on the d-dimensional box-cover number that is better than all previous bounds, in a sense close to best possible. We also improve the best bound known in 3 dimensions from 314 to 64 and propose possible further improvements through finding the maximum domination number over parity tournaments. [Copyright &y& Elsevier]

Chudnovsky and Seymour proved that every connected claw-free graph that contains a stable set of size 3 has chromatic number at most twice its clique number. We improve this for small clique size, showing that every claw-free graph with clique number at most 3 is 4-choosable and every claw-free graph with clique number at most 4 is 7-choosable. These bounds are tight. [ABSTRACT FROM AUTHOR]

R. H. Schelp conjectured that if G is a graph with |V(G)| = R(Pn, Pn) such that δ(G) > $$\frac{3|V(G)|}{ 4}$, then in every 2-colouring of the edges of G there is a monochromatic Pn. In other words, the Ramsey number of a path does not change if the graph to be coloured is not complete but has large minimum degree.Here we prove Ramsey-type results that imply the conjecture in a weakened form, first replacing the path by a matching, showing that the star-matching–matching Ramsey number satisfying R(Sn, nK2, nK2) = 3n − 1. This extends R(nK2, nK2) = 3n − 1, an old result of Cockayne and Lorimer. Then we extend this further from matchings to connected matchings, and outline how this implies Schelp's conjecture in an asymptotic sense through a standard application of the Regularity Lemma.It is sad that we are unable to hear Dick Schelp's reaction to our work generated by his conjecture. [ABSTRACT FROM PUBLISHER]

Abstract: Let be the largest integer with the following property: if the edges of the complete 3-uniform hypergraph are colored with colors then there is a monochromatic component with at least vertices. Here we show that and . Both results are sharp under suitable divisibility conditions (namely if is divisible by 7, or by 6 respectively). [Copyright &y& Elsevier]

We show that if a sequence of trees T1, T2, ..., Tn-1 can be packed into Kn then they can be also packed into any n-chromatic graph. [ABSTRACT FROM AUTHOR]

Abstract: It is a well-known proposition that every graph of chromatic number larger than contains every tree with edges. The ‘standard’ reasoning is that such a graph must contain a subgraph of minimum degree at least . Bohman, Frieze, and Mubayi noticed that, although this argument does not work for hypergraphs, it is still possible that the proposition holds for hypergraphs as well. Indeed, Loh recently proved that every uniform hypergraph of chromatic number larger than contains every hypertree with edges. Here we observe that the basic property of the well-known greedy algorithm immediately implies a much more general result (with a conceptually simpler proof): if the greedy algorithm colors the vertices of an -uniform hypergraph with more than colors then the hypergraph contains every -uniform hypertree with edges. [ABSTRACT FROM AUTHOR]