Size Ramsey numbers of stars versus cliques

The size Ramsey number of two graphs and is the smallest integer such that there exists a graph on edges with the property that every red-blue colouring of the edges of yields a red copy of or a blue copy of . In 1981, Erdős observed that and he conjectured that this upper bound on is sharp. In 1983, Faudree and Sheehan extended this conjecture as follows: They proved the case . In 2001, Pikhurko showed that this conjecture is not true for and , by disproving the mentioned conjecture of Erdős. Here, we prove Faudree and Sheehan's conjecture for a given and .     

A note on Ramsey size‐linear graphs

We show that if G is a Ramsey size‐linear graph and x,y ∈ V (G) then if we add a sufficiently long path between x and y we obtain a new Ramsey size‐linear graph. As a consequence we show that if G is any graph such that every cycle in G contains at least four consecutive vertices of degree 2 then G is Ramsey size‐linear. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 1–5, 2002     

CO‐irredundant Ramsey numbers for graphs

The study of the CO‐irredundant Ramsey numbers t(n₁, ···, n_k) is initiated. It is shown that several values and bounds for these numbers may be obtained from the well‐studied generalized graph Ramsey numbers and the values of t(4, 5), t(4, 6) and t(3, 3, m) are calculated. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 258–268, 2000     

On graphs with small Ramsey numbers*

Let R(G) denote the minimum integer N such that for every bicoloring of the edges of K_N, at least one of the monochromatic subgraphs contains G as a subgraph. We show that for every positive integer d and each γ,0 < γ < 1, there exists k = k(d,γ) such that for every bipartite graph G = (W,U;E) with the maximum degree of vertices in W at most d and , . This answers a question of Trotter. We give also a weaker bound on the Ramsey numbers of graphs whose set of vertices of degree at least d + 1 is independent. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 198–204, 2001     

Size Ramsey numbers for some regular graphs

P. Erdös, R.J. Faudree, C.C. Rousseau and R.H. Schelp [P. Erdös, R.J. Faudree, C.C. Rousseau, R.H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978) 145-161] studied the asymptotic behaviour of for certain graphs G,H. In this paper there will be given a lower bound for the diagonal size Ramsey number of K_n,n,n. The result is a generalization of a theorem for K_n,n given by P. Erdös and C.C. Rousseau [P. Erdös, C.C. Rousseau, The size Ramsey numbers of a complete bipartite graph, Discrete Math. 113 (1993) 259-262].Moreover, an open question for bounds for size Ramsey number of each n-regular graph of order n+t for t>n−1 is posed.     

On graphs with subgraphs having large independence numbers

Let G be a graph on n vertices in which every induced subgraph on vertices has an independent set of size at least . What is the largest so that every such G must contain an independent set of size at least q? This is one of the several related questions raised by Erd?s and Hajnal. We show that , investigate the more general problem obtained by changing the parameters s and t, and discuss the connection to a related Ramsey‐type problem. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 149–157, 2007     

On ramsey numbers of forests versus nearly complete graphs

A formula is presented for the ramsey number of any forest of order at least 3 versus any graph G of order n ≥ 4 having clique number n - 1. In particular, if T is a tree of order m ≥ 3, then r(T, G) = 1 + (m - 1)(n - 2).     

On the Size‐Ramsey Number of Hypergraphs

The size‐Ramsey number of a graph G is the minimum number of edges in a graph H such that every 2‐edge‐coloring of H yields a monochromatic copy of G. Size‐Ramsey numbers of graphs have been studied for almost 40 years with particular focus on the case of trees and bounded degree graphs. We initiate the study of size‐Ramsey numbers for k‐uniform hypergraphs. Analogous to the graph case, we consider the size‐Ramsey number of cliques, paths, trees, and bounded degree hypergraphs. Our results suggest that size‐Ramsey numbers for hypergraphs are extremely difficult to determine, and many open problems remain.     

Mean Ramsey–Turán numbers

A ρ‐mean coloring of a graph is a coloring of the edges such that the average number of colors incident with each vertex is at most ρ. For a graph H and for ρ ≥ 1, the mean Ramsey–Turán number RT(n, H,ρ ? mean) is the maximum number of edges a ρ‐mean colored graph with n vertices can have under the condition it does not have a monochromatic copy of H. It is conjectured that where is the maximum number of edges a k edge‐colored graph with n vertices can have under the condition it does not have a monochromatic copy of H. We prove the conjecture holds for . We also prove that . This result is tight for graphs H whose clique number equals their chromatic number. In particular, we get that if H is a 3‐chromatic graph having a triangle then . © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 126–134, 2006     

没有K4-图子式的图的无圈边色数

一个图G 的无圈k- 边染色是指G 的一个正常的不产生双色圈的k- 边染色. G 的无圈边色数a′(G) 定义为使得G 有一个无圈k- 边染色的最小的整数k. 本文完全刻画了最大度不为4 的没有K₄-图子式的图的无圈边色数.     

On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs

The well‐known Ramsey number is the smallest integer n such that every ‐free graph of order n contains an independent set of size u. In other words, it contains a subset of u vertices with no K₂. Erd?s and Rogers introduced a more general problem replacing K₂ by  for . Extending the problem of determining Ramsey numbers they defined the numbers where the minimum is taken over all ‐free graphs G of order n. In this note, we study an analogous function for 3‐uniform hypergraphs. In particular, we show that there are constants c₁ and c₂ depending only on s such that      

Every 4‐Colorable Graph With Maximum Degree 4 Has an Equitable 4‐Coloring

Chen et al., conjectured that for r≥3, the only connected graphs with maximum degree at most r that are not equitably r‐colorable are K_{r, r} (for odd r) and K_{r + 1}. If true, this would be a joint strengthening of the Hajnal–Szemerédi theorem and Brooks' theorem. Chen et al., proved that their conjecture holds for r = 3. In this article we study properties of the hypothetical minimum counter‐examples to this conjecture and the structure of “optimal” colorings of such graphs. Using these properties and structure, we show that the Chen–Lih–Wu Conjecture holds for r≤4. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:31–48, 2012     

On Ramsey numbers of uniform hypergraphs with given maximum degree

For every ?>0 and every positive integers Δ and r, there exists C=C(?,Δ,r) such that the Ramsey number, R(H,H) of any r-uniform hypergraph H with maximum degree at most Δ is at most C|V(H)|^1+?.     

Short odd cycles in 4‐chromatic graphs

It is shown that any 4‐chromatic graph on n vertices contains an odd cycle of length smaller than √8n. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 145–147, 1999     

Upper bounds for ramsey numbers R(3, 3, ⋖, 3) and Schur numbers

In this paper we show that for n ≥ 4, R(3, 3, ⋖, 3) < + 1. Consequently, a new bound for Schur numbers is also given. Also, for even n ≥ 6, the Schur number S_n is bounded by S_n < - n + 2. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 119–122, 1997     

All cycle‐complete graph Ramsey numbers r(Cm,K6)

The cycle‐complete graph Ramsey number r(C_m, K_n) is the smallest integer N such that every graph G of order N contains a cycle C_m on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(C_m, K_n) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C₃, K₃) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n² ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003     

Anti‐Ramsey numbers of doubly edge‐critical graphs

Given a graph H and a positive integer n, Anti‐Ramsey number AR(n, H) is the maximum number of colors in an edge‐coloring of K_n that contains no polychromatic copy of H. The anti‐Ramsey numbers were introduced in the 1970s by Erd?s, Simonovits, and Sós, who among other things, determined this function for cliques. In general, few exact values of AR(n, H) are known. Let us call a graph H doubly edge‐critical if χ(H?e)≥p+ 1 for each edge e∈E(H) and there exist two edges e₁, e₂ of H for which χ(H?e₁?e₂)=p. Here, we obtain the exact value of AR(n, H) for any doubly edge‐critical H when n?n₀(H) is sufficiently large. A main ingredient of our proof is the stability theorem of Erd?s and Simonovits for the Turán problem. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 210–218, 2009     

On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results

A vertex k-coloring of graph G is distinguishing if the only automorphism of G that preserves the colors is the identity map. It is proper-distinguishing if the coloring is both proper and distinguishing. The distinguishing number ofG, D(G), is the smallest integer k so that G has a distinguishing k-coloring; the distinguishing chromatic number ofG, χ_D(G), is defined similarly.It has been shown recently that the distinguishing number of a planar graph can be determined efficiently by counting a related parameter-the number of inequivalent distinguishing colorings of the graph. In this paper, we demonstrate that the same technique can be used to compute the distinguishing number and the distinguishing chromatic number of an interval graph. We make use of PQ-trees, a classic data structure that has been used to recognize and test the isomorphism of interval graphs; our algorithms run in O(n³log³n) time for graphs with n vertices. We also prove a number of results regarding the computational complexity of determining a graph’s distinguishing chromatic number.