Search

We call a proper edge coloring of a graph G $G$ a B‐coloring if every 4‐cycle of G $G$ is colored with four different colors. Let q B( G ) ${q}_{B}(G)$ denote the smallest number of colors needed for a B‐coloring of G $G$. Motivated by earlier papers on B‐colorings, here we consider q B( G ) ${q}_{B}(G)$ for planar and outerplanar graphs in terms of the maximum degree Δ = Δ( G ) ${\rm{\Delta }}={\rm{\Delta }}(G)$. We prove that q B( G ) ≤ 2 Δ + 8 ${q}_{B}(G)\le 2{\rm{\Delta }}+8$ for planar graphs, q B( G ) ≤ 2 Δ ${q}_{B}(G)\le 2{\rm{\Delta }}$ for bipartite planar graphs, and q B( G ) ≤ Δ + 1 ${q}_{B}(G)\le {\rm{\Delta }}+1$ for outerplanar graphs with Δ ≥ 4 ${\rm{\Delta }}\ge 4$. We conjecture that, for Δ ${\rm{\Delta }}$ sufficiently large, q B( G ) ≤ 2 Δ( G ) ${q}_{B}(G)\le 2{\rm{\Delta }}(G)$ for planar G $G$, and q B( G ) ≤ Δ( G ) ${q}_{B}(G)\le {\rm{\Delta }}(G)$ for outerplanar G $G$. [ABSTRACT FROM AUTHOR]

We study two well‐known Ramsey‐type problems for (vertex‐)ordered complete graphs. Two independent edges in ordered graphs can be nested, crossing, or separated. Apart from two trivial cases, these relations define six types of subgraphs, depending on which one (or two) of these relations are forbidden. Our first target is to refine a remark by Erdős and Rado that every 2‐coloring of the edges of a complete graph contains a monochromatic spanning tree. We show that forbidding one relation we always have a monochromatic (nonnested, noncrossing, and nonseparated) spanning tree in a 2‐edge‐colored ordered complete graph. On the other hand, if two relations are forbidden, then it is possible that we have monochromatic (nested, separated, and crossing) subtrees of size only ~n∕2 $\unicode{x0007E}n\unicode{x02215}2$ in a 2‐colored ordered complete graph on n $n$ vertices. Some of these results relate to drawings of complete graphs. For instance, the existence of a monochromatic nonnested spanning tree in 2‐colorings of ordered complete graphs verifies a more general conjecture for twisted drawings. Our second subject is to refine the Ramsey number of matchings, that is, pairwise independent edges for ordered complete graphs. Cockayne and Lorimer proved that for given positive integers t,n $t,n$, m=(t−1)(n−1)+2n $m=(t-1)(n-1)+2n$ is the smallest integer with the following property: every t $t$‐coloring of the edges of a complete graph Km ${K}_{m}$ contains a monochromatic matching with n $n$ edges. We conjecture that this result can be strengthened: t $t$‐colored ordered complete graphs on m $m$ vertices contain monochromatic nonnested and also nonseparated matchings with n $n$ edges. We prove this conjecture for some special cases including the following. (i) Every t $t$‐colored ordered complete graph on t+3 $t+3$ vertices contains a monochromatic nonnested matching of size two (n=2 $n=2$ case). We prove it by showing that the chromatic number of the subgraph of the Kneser graph induced by the nonnested 2‐matchings in an ordered complete graph on t+3 $t+3$ vertices is (t+1) $(t+1)$‐chromatic.(ii) Every 2‐colored ordered complete graph on 3n−1 $3n-1$ vertices contains a monochromatic nonseparated matching of size n $n$ (t=2 $t=2$ case). This is the hypergraph analog of a result of Kaiser and Stehlík who proved that the Kneser graph induced by the nonseparated 2‐matchings in an ordered complete graph on t+3 $t+3$ vertices is (t+1) $(t+1)$‐chromatic. For nested, separated, and crossing matchings the situation is different. The smallest m $m$ ensuring a monochromatic matching of size n $n$ in every t $t$‐coloring is 2(t(n−1))+1) $2(t(n-1))+1)$ in the first two cases and one less in the third case. [ABSTRACT FROM AUTHOR]

Related to the famous (7,4)-problem, in an earlier paper we introduced B-colorings. We call a proper edge coloring of a graph G a B-coloring if every 4-cycle of G is colored with four different colors. Let q B (G) denote the smallest number of colors needed for a B-coloring of G. Here we look at q B (G) for Cartesian products of paths and cycles. Our main result is that q B (G) is equal to the chromatic index of G for grids, i.e. for Cartesian products of paths (apart from a few exceptions). This extends an earlier result for the case when G is the d-dimensional cube. Our main tool is a lemma which gives q B (G □ H) ≤ q B (G) + q B (H) if χ (G) ≤ q B (H) , χ (H) ≤ q B (G) , where χ (G) is the chromatic number of G. [ABSTRACT FROM AUTHOR]

A digraph is d $d$‐dominating if every set of at most d $d$ vertices has a common out‐neighbor. For all integers d≥2 $d\ge 2$, let f(d) $f(d)$ be the smallest integer such that the vertices of every 2‐edge‐colored (finite or infinite) complete digraph (including loops) can be covered by the vertices of at most f(d) $f(d)$ monochromatic d $d$‐dominating subgraphs. Note that the existence of f(d) $f(d)$ is not obvious – indeed, the question which motivated this paper was simply to determine whether f(d) $f(d)$ is bounded, even for d=2 $d=2$. We answer this question affirmatively for all d≥2 $d\ge 2$, proving 4≤f(2)≤8 $4\le f(2)\le 8$ and 2d≤f(d)≤2ddd−1d−1for alld≥3 $2d\le f(d)\le 2d\left(\frac{{d}^{d}-1}{d-1}\right)\,\,\text{for all}\,\,d\ge 3$. We also give an example to show that there is no analogous bound for more than two colors. Our result provides a positive answer to a question regarding an infinite analogue of the Burr‐Erdős conjecture on the Ramsey numbers of d $d$‐degenerate graphs. Moreover, a special case of our result is related to properties of d $d$‐paradoxical tournaments. [ABSTRACT FROM AUTHOR]

A path-matching of order p is a vertex disjoint union of nontrivial paths spanning p vertices. Burr and Roberts, and Faudree and Schelp determined the 2-color Ramsey number of path-matchings. In this paper we study the multicolor Ramsey number of path-matchings. Given positive integers r , p 1 , ... , p r , define R P M (p 1 , ... , p r) to be the smallest integer n such that in any r -coloring of the edges of K n there exists a path-matching of color i and order at least p i for some i ∈ r. Our main result is that for r ≥ 2 and p 1 ≥ ... ≥ p r ≥ 2 , if p 1 ≥ 2 r − 2 , then R P M (p 1 , ... , p r) = p 1 − (r − 1) + ∑ i = 2 r ⌈ p i 3 ⌉. Perhaps surprisingly, we show that when p 1 < 2 r − 2 , it is possible that R P M (p 1 , ... , p r) is larger than p 1 − (r − 1) + ∑ i = 2 r ⌈ p i 3 ⌉ , but in any case we determine the correct value to within a constant (depending on r); i.e. p 1 − (r − 1) + ∑ i = 2 r ⌈ p i 3 ⌉ ≤ R P M (p 1 , ... , p r) ≤ ⌈ p 1 − r 3 + ∑ i = 2 r p i 3 ⌉. As a corollary we get that in every r -coloring of K n there is a monochromatic path-matching of order at least 3 ⌊ n r + 2 ⌋ , which is essentially best possible. We also determine R P M (p 1 , ... , p r) in all cases when the number of colors is at most 4. The proof of the main result uses a minimax theorem for path-matchings derived from a result of Las Vergnas (extending Tutte's 1-factor theorem) to show that the value of R P M (p 1 , ... , p r) depends on the block sizes in covering designs (which can be also formulated in terms of monochromatic 1-cores in colored complete graphs). While block sizes in covering designs have been studied intensively before, they seem to have only been studied in the uniform case (when all block sizes are equal). Then we obtain the result above by giving estimates on the block sizes in covering designs in the arbitrary (non-uniform) case. [ABSTRACT FROM AUTHOR]

According to Mantel's theorem, a triangle-free graph on n points has at most n 2 / 4 edges. A linear k-graph is a set of points together with some k-element subsets, called edges, such that any two edges intersect in at most one point. The k-graph Fk, called a fan, consists of k edges that pairwise intersect in exactly one point v, plus one more edge intersecting each of these edges in a point different from v. We extend Mantel's theorem as follows: fan-free linear k-graphs on n points have at most n 2 / k 2 edges. This extension nicely illustrates the difficulties of hypergraph Turán problems. The determination of the case of equality leads to transversal designs on n points with k groups—for k = 3 these are equivalent to Latin squares. However, in contrast to the graph case, new structures and open problems emerge when n is not divisible by k. [ABSTRACT FROM AUTHOR]

Abstract For a graph G = (V , E) , a hypergraph H is called Berge- G if there is a bijection ϕ : E (G) → E (H) such that for each e ∈ E (G) , e ⊆ ϕ (e). The set of all Berge- G hypergraphs is denoted B (G). For integers k ≥ 2 , r ≥ 2 , and a graph G , let the Ramsey number R r (B (G) , k) be the smallest integer n such that no matter how the edges of a complete r -uniform n -vertex hypergraph are colored with k colors, there is a copy of a monochromatic Berge- G subhypergraph. Furthermore, let R (B (G) , k) be the smallest integer n such that no matter how all subsets of an n -element set are colored with k colors, there is a monochromatic copy of a Berge- G hypergraph. We give an upper bound for R r (B (G) , k) in terms of graph Ramsey numbers. In particular, we prove that when G becomes acyclic after removing some vertex, R r (B (G) , k) ≤ 4 k | V (G) | + r − 2 , in contrast with classical multicolor Ramsey numbers. When G is a triangle (or a K 4), we find sharper bounds and some exact results and determine some "small" Ramsey numbers: • k ∕ 2 − o (k) ≤ R 3 (B (K 3) , k) ≤ 3 k ∕ 4 + o (k) , • For any odd integer t ≠ 3 , R (B (K 3) , 2 t − 1) = t + 2 , • 2 c k ≤ R 3 (B (K 4) , k) ≤ e (1 + o (1)) (k − 1) k ! , • R 3 (B (K 3) , 2) = R 3 (B (K 3) , 3) = 5 , R 3 (B (K 3) , 4) = 6 , R 3 (B (K 3) , 5) = 7 , R 3 (B (K 3) , 6) = 8 , R 3 (B (K 3) , 8) = 9 , R 3 (B (K 4) , 2) = 6. [ABSTRACT FROM AUTHOR]

A Berge-K4 in a triple system is a configuration with four vertices v1, v2, v3, v4 and six distinct triples {eij: 1 ≤ i < j ≤ 4} such that{ui, vj}⊂ eij for every 1 ≤ i < j ≤ 4. We denote by B the set of Berge-K4 configurations. A triple system is B -free if it does not contain any member of B . We prove that the maximum number of triples in a B -free triple system on n ≥ 6 points is obtained by the balanced complete 3-partite triple system: all triples {abc: a ϵ A, b ϵ B, c ϵ C} where A,B,C is a partition of n points with [n/3]= |A| ≤|B| ≤ |C| = n/33 [ABSTRACT FROM AUTHOR]

We call a partial Steiner triple system C (configuration) t-Ramsey if for large enough n (in terms of [ABSTRACT FROM AUTHOR]

A well-known special case of a conjecture attributed to Ryser (actually appeared in the thesis of Henderson (1971)) states that k -partite intersecting hypergraphs have transversals of at most k − 1 vertices. An equivalent form of the conjecture in terms of coloring of complete graphs is formulated in Gyárfás (1977): if the edges of a complete graph K are colored with k colors then the vertex set of K can be covered by at most k − 1 sets, each forming a connected graph in some color. It turned out that the analogue of the conjecture for hypergraphs can be answered: it was proved in Király (2013) that in every k -coloring of the edges of the r -uniform complete hypergraph K r ( r ≥ 3 ), the vertex set of K r can be covered by at most ⌈ k ∕ r ⌉ sets, each forming a connected hypergraph in some color. Here we investigate the analogue problem for complete r -uniform r -partite hypergraphs. An edge coloring of a hypergraph is called spanning if every vertex is incident to edges of every color used in the coloring. We propose the following analogue of Ryser’s conjecture. In every spanning ( r + t ) - coloring of the edges of a complete r -uniform r -partite hypergraph, the vertex set can be covered by at most t + 1 sets, each forming a connected hypergraph in some color . We show that the conjecture (if true) is best possible. Our main result is that the conjecture is true for 1 ≤ t ≤ r − 1 . We also prove a slightly weaker result for t ≥ r , namely that t + 2 sets, each forming a connected hypergraph in some color, are enough to cover the vertex set. To build a bridge between complete r -uniform and complete r -uniform r -partite hypergraphs, we introduce a new notion. A hypergraph is complete r -uniform ( r , ℓ ) -partite if it has all r -sets that intersect each partite class in at most ℓ vertices (where 1 ≤ ℓ ≤ r ). Extending our results achieved for ℓ = 1 , we prove that for any r ≥ 3 , 2 ≤ ℓ ≤ r , k ≥ 1 + r − ℓ , in every spanning k -coloring of the edges of a complete r -uniform ( r , ℓ ) -partite hypergraph, the vertex set can be covered by at most 1 + ⌊ k − r + ℓ − 1 ℓ ⌋ sets, each forming a connected hypergraph in some color. [ABSTRACT FROM AUTHOR]

To celebrate the 40th anniversary of EJC, I share some problems close to my heart. They relate mainly to two areas I became acquainted with more than 50 years ago during my years as a student at the Eötvös University, Budapest. I was fascinated by Ramsey theory learned at the course of Vera T. Sós and the notion of perfect graphs and related structures learned from Erdős and Gallai. I was also impressed by the early developments of hypergraph theory led by Berge and his French school. [ABSTRACT FROM AUTHOR]

This paper extends to hypergraphs a question discussed in Bialostocki and Gyárfás [4] and Garrison [8]: can one generalize a Ramsey type result from complete host graphs to graphs of sufficiently large chromatic number? For an r -uniform tree T ( r ≥ 2 ) we define the ( t -color) chromatic Ramsey number χ ( T , t ) as the smallest m with the following property: if the edges of any m -chromatic r -uniform hypergraph are colored with t colors in any manner, there is a monochromatic copy of T . The presence of a tree is not accidental: χ ( H , t ) can be defined only for an acyclic hypergraph H since there are hypergraphs with arbitrary large chromatic number and girth. We prove that R r ( T , t ) − 1 r − 1 + 1 ≤ χ ( T , t ) ≤ | E ( T ) | t + 1 where R r ( T , t ) is the t -color Ramsey number of T . We give better upper bounds for χ ( T , t ) when T is a matching or a star, proving that for r ≥ 2 , k ≥ 1 , t ≥ 1 , χ ( M k r , t ) ≤ ( t − 1 ) ( k − 1 ) + 2 k and χ ( S k r , t ) ≤ t ( k − 1 ) + 2 where M k r and S k r are, respectively, the r -uniform matching and star with k edges. The general upper bounds are improved for 3 -uniform hypergraphs. We prove that χ ( M k 3 , 2 ) = 2 k , extending a special case of Alon–Frankl–Lovász theorem. We also prove that χ ( S 2 3 , t ) ≤ t + 1 , which is sharp for t = 2 , 3 . This is a corollary of our main result which bounds the chromatic number χ ( H ) of 3 -uniform hypergraphs by the chromatic number of its 1-intersection graph H [ 1 ] , whose vertices represent hyperedges and whose edges represent intersections of hyperedges in exactly one vertex. We prove that χ ( H ) ≤ χ ( H [ 1 ] ) for any 3 -uniform hypergraph H (assuming that H [ 1 ] has at least one edge). The proof uses the list coloring version of Brooks’ theorem. The more general question, whether χ ( H ) ≤ χ ( H [ 1 ] ) holds for every r -uniform hypergraph ( r > 3 ) remains open. We could not decide either whether the above lower bound of χ ( T , t ) is sharp for every r -uniform tree. [ABSTRACT FROM AUTHOR]

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

A linear triple system is a 3-uniform hypergraph H = (V , E) , where E is a set of three-element subsets of V such that any two edges intersect in at most one vertex. For linear triple systems H , F we say that H is F-free if H does not contain any subsystem isomorphic to F. We consider F fixed and call it a configuration. The (linear) Turán number ex L (n , F) (or simply just ex (n , F)) of a configuration F is the maximum number of edges in F -free linear triple systems with n vertices. Here we call attention to some properties of the wicket W , formed by three rows and two columns of a 3 × 3 point matrix. On one hand we show that the problem whether ex (n , F) = o (n 2) can be decided for all configurations with at most five edges, except for F = W , which remains undecided. On the other hand we prove that ex (n , W) ≤ (1 − c) n 2 6 with some c > 0 , separating it from the conjectured asymptotic of ex (n , G 3 × 3) , where G 3 × 3 , the grid , formed by three rows and three columns of a 3 × 3 point matrix. [ABSTRACT FROM AUTHOR]

This survey is devoted to problems and results concerning covering the vertices of edge colored graphs or hypergraphs with monochromatic paths, cycles and other objects. It is an expanded version of the talk with the same title at the Seventh Cracow Conference on Graph Theory, held in Rytro in September 14–19, 2014. [ABSTRACT FROM AUTHOR]

It is well-known (as a special case of the path–path Ramsey number) that in every 2-coloring of the edges of K 3 n − 1 , the complete graph on 3 n − 1 vertices, there is a monochromatic P 2 n , a path on 2 n vertices. Schelp conjectured that this statement remains true if K 3 n − 1 is replaced by any host graph on 3 n − 1 vertices with minimum degree at least 3 ( 3 n − 1 ) 4 . Here we propose the following stronger conjecture, allowing host graphs with the corresponding Ore-type condition: If G is a graph on 3 n − 1 vertices such that for any two non-adjacent vertices u and v , d G ( u ) + d G ( v ) ≥ 3 2 ( 3 n − 1 ) , then in any 2-coloring of the edges of G there is a monochromatic path on 2 n vertices. Our main result proves the conjecture in a weaker form, replacing P 2 n by a connected matching of size n . Here a monochromatic, say red, matching in a 2-coloring of the edges of a graph is connected if its edges are all in the same connected component of the graph defined by the red edges. Applying the standard technique of converting connected matchings to paths with the Regularity Lemma, we use this result to get an asymptotic version of our conjecture for paths. [ABSTRACT FROM AUTHOR]

A cross-free set of size m in a Steiner triple system [ABSTRACT FROM AUTHOR]

The typical problem in (generalized) Ramsey theory is to find the order of the largest monochromatic member of a family $${\mathcal{F}}$$ (for example matchings, paths, cycles, connected subgraphs) that must be present in any edge coloring of a complete graph K with t colors. Another area is to find the minimum number of monochromatic members of $${\mathcal{F}}$$ that partition or cover the vertex set of every edge colored complete graph. Here we propose a problem that connects these areas: for a fixed positive integers s ≤ t, at least how many vertices can be covered by the vertices of no more than s monochromatic members of $${\mathcal{F}}$$ in every edge coloring of K with t colors. Several problems and conjectures are presented, among them a possible extension of a well-known result of Cockayne and Lorimer on monochromatic matchings for which we prove an initial step: every t-coloring of K contains a ( t − 1)-colored matching of size k provided that [ABSTRACT FROM AUTHOR]

Abstract: In this paper we show that properly edge-colored graphs with have rainbow matchings of size ; this gives the best known bound for a recent question of Wang. We also show that properly edge-colored graphs with have rainbow matchings of size at least . This result extends (with a weaker error term) the well-known result that a factorization of the complete bipartite graph has a rainbow matching of size , or equivalently that every Latin square of order has a partial transversal of size (an asymptotic version of the Ryser–Brualdi conjecture). In this direction we also show that every Latin square of order has a cycle-free partial transversal of size . [Copyright &y& Elsevier]

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]

Abstract: Given an -uniform hypergraph , the multicolor Ramsey number is the minimum such that every -coloring of the edges of the complete -uniform hypergraph yields a monochromatic copy of . We investigate when grows and is fixed. For nontrivial -uniform hypergraphs , the function ranges from to double exponential in . We observe that is polynomial in when is -partite and at least single-exponential in otherwise. Erdős, Hajnal and Rado gave bounds for large cliques with , showing its correct exponential tower growth. We give a proof for cliques of all sizes, , using a slight modification of the celebrated stepping-up lemma of Erdős and Hajnal. For -uniform hypergraphs, we give an infinite family with sub-double-exponential upper bound and show connections between graph and hypergraph Ramsey numbers. Specifically, we prove that where is obtained from by deleting an edge. We provide some other bounds, including single-exponential bounds for as well as asymptotic or exact values of when is the bow , kite , tight path or the windmill . We also determine many new “small” Ramsey numbers and show their relations to designs. For example, the lower bound for is demonstrated by decomposing the triples of a seven element set into six partial STS (two of them are Fano planes). [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]

Let G=(V,E) be a τ‐critical graph with τ(G)=t. Erdős and Gallai proved that ∣V∣≤2t and the bound ∣E∣≤t+12 was obtained by Erdős, Hajnal, and Moon. We give here the sharp combined bound ∣E∣+∣V∣≤t+22 and find all graphs with equality. [ABSTRACT FROM AUTHOR]

The Turán number of hypergraphs has been studied extensively. Here we deal with a recent direction, the linear Turán number, and restrict ourselves to linear triple systems, a collection of triples on a set of points in which any two triples intersect in at most one point. For a fixed linear triple system F , the linear Turán number ex L (n , F) is the maximum number of triples in a linear triple system with n points that does not contain F as a subsystem. We initiate the study of the linear Turán number for an acyclic F. In this case ex L (n , F) is linear in n and we aim for good bounds. Since the case of trees is already difficult for graphs (Erdős–Sós conjecture), we concentrate on matchings, paths and small trees. In case of matchings, where M k is the set of k pairwise disjoint triples, we prove that for fixed k and large enough n , ex L (n , M k) = f (n , k) where f (n , k) is the maximum number of triples that can meet k − 1 points in a linear triple system on n points. This is an analogue of an old result of Erdős on hypergraph matchings. For the k -edge linear path P k we show (extending some standard path increasing methods used for graphs) that ex L (n , P k) ≤ 1. 5 k n which is probably far from best possible. Finding ex L (n , F) relates to difficult problems on Steiner triple systems and interesting even for small trees. For example, for P 4 , the path with four triples, ex L (n , P 4) ≤ 4 n 3 with equality only for disjoint union of affine planes of order 3. On the other hand, for E 4 , the tree having three pairwise disjoint triples and a fourth one meeting all of them, we have bounds only: 6 ⌊ n − 3 4 ⌋ ≤ ex L (n , E 4) ≤ 2 n. [ABSTRACT FROM AUTHOR]

Gallai-colorings of complete graphs-edge colorings such that no triangle is colored with three distinct colors-occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper), information theory and the theory of perfect graphs. A basic property of Gallai-colorings with at least three colors is that at least one of the color classes must span a disconnected graph. We are interested here in whether this or a similar property remains true if we consider colorings that do not contain a rainbow copy of a fixed graph F. We show that such graphs F are very close to bipartite graphs, namely, they can be made bipartite by the removal of at most one edge. We also extend Gallai's property for two infinite families and show that it also holds when F is a path with at most six vertices. [ABSTRACT FROM AUTHOR]

A coloring of the edges of the r-uniform complete hypergraph is a Gr-coloring if there is no rainbow simplex; that is, every set of r + 1 vertices contains two edges of the same color. The notion extends G2-colorings which are often called Gallai-colorings and originates from a seminal paper of Gallai. One well-known property of G2-colorings is that at least one color class has a spanning tree. J. Lehel and the senior author observed that this property does not hold for Gr-colorings and proposed to study fr(n), the size of the largest monochromatic component which can be found in every Gr-coloring of Krn, the complete r-uniform hypergraph. The previous remark says that f2(n) = n, and in this note, we address the case r = 3. We prove that [(n + 3)/2] ⩽ f3(n) ⩽ [4n/5], and this determines f3(n) for n < 7. We also prove that f3(7) = 6 by excluding certain 2-factors from the middle layer of the Boolean lattice on seven elements. [ABSTRACT FROM AUTHOR]

Assume that D is a digraph without cyclic triangles and its vertices are partitioned into classes A1, ..., A t of independent vertices. A set is called a dominating set of size | S| if for any vertex there is a w∈ U such that ( w, v)∈ E( D). Let β( D) be the cardinality of the largest independent set of D whose vertices are from different partite classes of D. Our main result says that there exists a h = h(β( D)) such that D has a dominating set of size at most h. This result is applied to settle a problem related to generalized Gallai colorings, edge colorings of graphs without 3-colored triangles. © 2011 Wiley Periodicals, Inc. J Graph Theory [ABSTRACT FROM AUTHOR]

Abstract: The chromatic gap is the difference between the chromatic number and the clique number of a graph. Here we investigate , the maximum chromatic gap over graphs on n vertices. Can the extremal graphs be explored? While computational problems related to the chromatic gap are hopeless, an interplay between Ramsey-theory and matching theory leads to a simple and (almost) exact formula for in terms of Ramsey-numbers. For our purposes it is more convenient to work with the covering gap, the difference between the clique cover number and stability number of a graph and this is what we call the gap of a graph. Notice that the well-studied family of perfect graphs are the graphs whose induced subgraphs have gap zero. The maximum of the (covering) gap and the chromatic gap running on all induced subgraphs will be called perfectness gap. Using for the cardinality of a largest stable (independent) set of a graph G, we define where the minimum is taken over triangle-free graphs on n vertices. It is easy to observe that is essentially an inverse Ramsey function, defined by the relation . Our main result is that , possibly with the exception of small intervals (of length at most 15) around the Ramsey-numbers , where the error is at most 3. The central notions in our investigations are the gap-critical and the gap-extremal graphs. A graph G is gap-critical if for every proper induced subgraph , and gap-extremal if it is gap-critical with as few vertices as possible (among gap-critical graphs of the same gap). The strong perfect graph theorem, solving a long standing conjecture of Berge that stimulated a broad area of research, states that gap-critical graphs with gap 1 are the holes (chordless odd cycles of length at least five) and antiholes (complements of holes). The next step, the complete description of gap-critical graphs with gap 2 would probably be a very difficult task. As a very first step, we prove that there is a unique 2-extremal graph, , the union of two disjoint (chordless) cycles of length five. In general, for , we denote by the smallest order of a graph with gap t and we call a graph is t-extremal if it has gap t and order . Equivalently, is the smallest order of a graph with perfectness gap equal to t. It is tempting to conjecture that with equality for the graph . However, for the graph has gap t but it is not gap-extremal (although gap-critical). We shall prove that , and . Somewhat surprisingly, after the uncertain values , , , we can show that . On the other hand we can easily show that is asymptotically equal to 2t, that is, is asymptotic to . According to our main result the gap is actually equal to , unless n is in an interval where R is a Ramsey-number, and if this exception occurs the gap may be larger than this value by only a small constant (at most 3). Our study provides some new properties of Ramsey graphs them selves: it shows that triangle-free Ramsey graphs have high matchability and connectivity properties, leading possibly to new bounds on Ramsey-numbers. [Copyright &y& Elsevier]

The Grundy number of a graph G is the largest k such that G has a greedy k-coloring, that is, a coloring with k colors obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this article, we give new bounds on the Grundy number of the product of two graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:78-88, 2012 [ABSTRACT FROM AUTHOR]

Edge colorings of r-uniform hypergraphs naturally define a multicoloring on the 2-shadow, i.e., on the pairs that are covered by hyperedges. We show that in any (r – 1)-coloring of the edges of an r-uniform hypergraph with n vertices and at least $$(1-\varepsilon)\left( {\begin{array}{*{20}c} n\\ r\\ \end{array}}\right)$$ edges, the 2-shadow has a monochromatic matching covering all but at most o( n) vertices. This result confirms an earlier conjecture and implies that for any fixed r and sufficiently large n, there is a monochromatic Berge-cycle of length (1 – o(1)) n in every ( r – 1)-coloring of the edges of $${K^{(r)}_{n}}$$, the complete r-uniform hypergraph on n vertices. [ABSTRACT FROM AUTHOR]

Abstract: Gallai-colorings of complete graphs–edge colorings such that no triangle is colored with three distinct colors–occur in various contexts such as the theory of partially ordered sets (in Gallai’s original paper), information theory and the theory of perfect graphs. We extend here Gallai-colorings to non-complete graphs and study the analogue of a basic result–any Gallai-colored complete graph has a monochromatic spanning tree–in this more general setting. We show that edge colorings of a graph without multicolored triangles contain monochromatic connected subgraphs with at least vertices, where is the independence number of . In general, we show that if the edges of an -uniform hypergraph are colored so that there is no multicolored copy of a fixed then there is a monochromatic connected subhypergraph such that where depends only on , , and . [Copyright &y& Elsevier]

Here we prove that for n ≥ 140, in every 3-coloring of the edges of $${K_n^{(4)}}$$ there is a monochromatic Berge cycle of length at least n − 10. This result sharpens an asymptotic result obtained earlier. Another result is that for n ≥ 15, in every 2-coloring of the edges of $${K_n^{(4)}}$$ there is a 3-tight Berge cycle of length at least n − 10. [ABSTRACT FROM AUTHOR]

Abstract: Here we prove a stability version of a Ramsey-type Theorem for paths. Thus in any 2-coloring of the edges of the complete graph we can either find a monochromatic path substantially longer than , or the coloring is close to the extremal coloring. [Copyright &y& Elsevier]

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 in every r-coloring of the edges of K n there is a monochromatic double star with at least $$\frac{n(r+1)+r-1}{r^2}$$ vertices. This result is sharp in asymptotic for r = 2 and for r≥ 3 improves a bound of Mubayi for the largest monochromatic subgraph of diameter at most three. When r-colorings are replaced by local r-colorings, our bound is $$\frac{n(r+1)+r-1}{r^2+1}$$ . [ABSTRACT FROM AUTHOR]

Abstract: We conjecture that for every 2-coloring of the edges of the complete graph contains a k-connected monochromatic subgraph with at least vertices. This conjecture, if true, is best possible. Here we prove it for , and show how to reduce it to the case . We prove the following result as well: for every 2-colored contains a k-connected monochromatic subgraph with at least vertices. [Copyright &y& Elsevier]

Abstract: We conjecture that for any fixed r and sufficiently large n, there is a monochromatic Hamiltonian Berge-cycle in every -coloring of the edges of , the complete r-uniform hypergraph on n vertices. We prove the conjecture for and its asymptotic version for . For general r we prove weaker forms of the conjecture: there is a Hamiltonian Berge-cycle in -colorings of for large n; and a Berge-cycle of order in -colorings of . The asymptotic results are obtained with the Regularity Lemma via the existence of monochromatic connected almost perfect matchings in the multicolored shadow graph induced by the coloring of . [Copyright &y& Elsevier]

Abstract: Improving a result of Erdős, Gyárfás and Pyber for large n we show that for every integer there exists a constant such that if and the edges of the complete graph are colored with r colors then the vertex set of can be partitioned into at most vertex disjoint monochromatic cycles. [Copyright &y& Elsevier]

Abstract: A -cycle of a hypergraph is a cycle including an edge that contains at least three base points of the cycle. We show that if a hypergraph has no -cycle, and , for every edge , then with equality if and only if H is obtained from a hypertree by doubling its edges. This result reminiscent of Berge''s and Lovász''s similar inequalities implies that 3-uniform hypergraphs with n vertices and n edges have -cycles, and 3-uniform simple hypergraphs with n vertices and edges have -cycles. Both results are sharp. Since the presence of a -cycle implies the presence of an odd cycle, both results are sharp for odd cycles as well. However, for linear 3-uniform hypergraphs the thresholds are different for -cycles and for odd cycles. Linear 3-uniform hypergraphs with n vertices and with minimum degree two have -cycles when and have odd cycles when and these are sharp results apart from the values of the constants. Most of our proofs use the concept of edge-critical (minimally 2-connected) graphs introduced by Dirac and by Plummer. In fact, the hypergraph results—in disguise—are extremal results for bipartite graphs that have no cycles with chords. [Copyright &y& Elsevier]

Abstract: Eroh and Oellermann defined as the smallest N such that any edge coloring of the complete bipartite graph contains either a monochromatic or a multicolored . We restate the problem of determining in matrix form and prove estimates and exact values for several choices of the parameters. Our general bound uses Füredi''s result on fractional matchings of uniform hypergraphs and we show that it is sharp if certain block designs exist. We obtain two sharp results for the case : we prove and that the smallest n for which any edge coloring of contains either a monochromatic or a multicolored is . [Copyright &y& Elsevier]

Fix t>1, a positive integer, and a=(a1,…,at) a vector of nonnegative integers. A t-coloring of the edges of a complete graph is called a-split if there exists a partition of the vertices into t sets V1,…,Vt such that every set of ai+1 vertices in Vi contains an edge of color i, for i=1,…,t. We combine a theorem of Deza with Ramsey's theorem to prove that, for any fixed a, the family of a-split colorings is characterized by a finite list of forbidden induced subcolorings. A similar hypergraph version follows from our proofs. These results generalize previous work by Ke´zdy et al. (J. Combin. Theory Ser. A 73(2) (1996) 353) and Gya´rfa´s (J. Combin. Theory Ser. A 81(2) (1998) 255). We also consider other notions of splitting. [Copyright &y& Elsevier]

Let p be a positive integer and let Q be a subset of {0,1,…,p}. Call p sets A1,A2,…,Ap of a ground set X a (p,Q)-system if the number of sets Ai containing x is in Q for every x ∈ X. In hypergraph terminology, a (p,Q)-system is a hypergraph with p edges such that each vertex x has degree d(x) ∈ Q. A family of sets F with ground set X is called (p,Q)-free if no p sets of F form a (p,Q)-system on X. We address the Tura´n-type problem for (p,Q)-systems: f(n,p,Q) is defined as max|F| over all (p,Q)-free families on the ground set [n] = {1,2,…,n}. We study the behavior of f(n,p,Q) when p and Q are fixed (allowing 2p+1 choices for Q) while n tends to infinity. The new results of this paper mostly relate to the middle zone where 2n−1&les;f(n,p,Q)&les;(1−c)2n (in this upper bound c depends only on p). This direction was initiated by Paul Erdo˝s who asked about the behavior of f(n,4,{0,3}). In addition, we give a brief survey on results and methods (old and recent) in the low zone (where f(n,p,Q) = o(2n)) and in the high zone (where 2n−(2−c)n). [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]

In this paper we study Turán and Ramsey numbers in linear triple systems, defined as 3-uniform hypergraphs in which any two triples intersect in at most one vertex. A famous result of Ruzsa and Szemerédi is that for any fixed c > 0 and large enough n the following Turán-type theorem holds. If a linear triple system on n vertices has at least c n 2 edges then it contains a triangle : three pairwise intersecting triples without a common vertex. In this paper we extend this result from triangles to other triple systems, called s -configurations. The main tool is a generalization of the induced matching lemma from a b a -patterns to more general ones. We slightly generalize s -configurations to extended s -configurations. For these we cannot prove the corresponding Turán-type theorem, but we prove that they have the weaker, Ramsey property: they can be found in any t -coloring of the blocks of any sufficiently large Steiner triple system. Using this, we show that all unavoidable configurations with at most 5 blocks, except possibly the ones containing the sail C 15 (configuration with blocks 123, 345, 561 and 147), are t -Ramsey for any t ≥ 1. The most interesting one among them is the wicket , D 4 , formed by three rows and two columns of a 3 × 3 point matrix. In fact, the wicket is 1-Ramsey in a very strong sense: all Steiner triple systems except the Fano plane must contain a wicket. [ABSTRACT FROM AUTHOR]

Abstract: An edge coloring of a graph is a local r coloring if the edges incident to any vertex are colored with at most r distinct colors. We determine the size of the largest monochromatic component that must occur in any local r coloring of a complete graph or a complete bipartite graph. [Copyright &y& Elsevier]

A Gallai coloring is an edge coloring that avoids triangles colored with three different colors. Given integers e 1 ≥ e 2 ≥ ⋯ ≥ e k with ∑ i = 1 k e i = n 2 for some n , does there exist a Gallai k -coloring of K n with e i edges in color i ? In this paper, we give several sufficient conditions and one necessary condition to guarantee a positive answer to the above question. In particular, we prove the existence of a Gallai-coloring if e 1 − e k ≤ 1 and k ≤ ⌊ n ∕ 2 ⌋. We prove that for any integer k ≥ 3 there is a (unique) integer g (k) with the following property: there exists a Gallai k -coloring of K n with e i edges in color i for every e 1 ≤ ⋯ ≤ e k satisfying ∑ i = 1 k e i = n 2 , if and only if n ≥ g (k). We show that g (3) = 5 , g (4) = 8 , and 2 k − 2 ≤ g (k) ≤ 8 k 2 + 1 for every k ≥ 3. [ABSTRACT FROM AUTHOR]

The t -color Ramsey problem for hypergraph matchings was settled by the well-known result of Alon, Frankl and Lovász (answering a conjecture of Erdős). This result was the last step in a chain of special cases most notably Lovász's solution to Kneser's problem. We proposed an extension of the Erdős problem: for given 1 ≤ s ≤ t , what is the maximum number of vertices that can be covered by a matching having at most s colors in every t -coloring of the edges of the complete graph K n (or hypergraph K n r). We revisit the first unknown case, r = 2 , s = 2 , t = 4 , where we conjectured that in every 4-coloring of K n there is a bicolored matching covering at least ⌊ 3 n ∕ 4 ⌋ vertices. We prove that this is true asymptotically by applying a recent twist of a standard application of the Regularity method: instead of lifting a (bicolored) matching of the reduced graph to regular cluster pairs, we lift a (bicolored) basic 2-matching , a subgraph whose connected components are edges and odd cycles. To find the bicolored basic 2-matching with at least ⌊ 3 n ∕ 4 ⌋ vertices in every 4-coloring of K n we use Tutte's minimax formula. [ABSTRACT FROM AUTHOR]

Abstract: Let denote the number of vertices of a graph G and let be the independence number of G, the maximum number of pairwise nonadjacent vertices of G. The Hall ratio of a graph G is defined bywhere the maximum is taken over all induced subgraphs H of G. It is obvious that every graph G satisfies where and denote the clique number and the chromatic number of G, respectively. We show that the interval can be arbitrary large by estimating the Hall ratio of the Mycielski graphs. [Copyright &y& Elsevier]

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]

Abstract: We propose the following conjecture to generalize results of Pósa and of Corrádi and Hajnal. Let be nonnegative integers and let be a graph with and minimal degree . Then contains a collection of vertex disjoint cycles, of them with a chord. We prove the conjecture for and for . The corresponding extremal problem, to find the minimum number of edges in a graph on vertices ensuring the existence of two vertex disjoint chorded cycles, is also settled. [Copyright &y& Elsevier]