Large induced forests in sparse graphs

For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and G ≠ K₄, then a(G) ≥ n ? e/4 ? 1/4 and this is sharp for all permissible e ≡ 3 (mod 4); and (b) if Δ ≥ 3, then a(G) ≥ α(G) + (n ? α(G))/(Δ ? 1)². Several problems remain open. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 113–123, 2001     

Sharp bounds for the number of 3‐independent partitions and the chromaticity of bipartite graphs

Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ??^?s(p,q) (resp., ??₂^?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph K_p,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ^?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? ₂^?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ^?s(p,q) (resp., G ∈ ?? ₂^?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ??^?s_i(p+i,q?i) where max and s_i = s ? i(p?q+i) (resp., a subset of ??₂^?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from K_p,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001     

On totally multicolored stars

Given an edge‐coloring of a graph G, a subgraph M of G will be called totally multicolored if no two edges of M receive the same color. Let h(G, K_1,q) be the minimum integer such that every edge‐coloring of G using exactly h(G, K_1,q) colors produces at least one totally multicolored copy of K_1,q (the q‐star) in G. In this article, an upper bound of h(G, K_1,q) is presented, as well as some applications of this upper bound. © 2005 Wiley Periodicals, Inc.     

There exist graphs with super‐exponential Ramsey multiplicity constant

The Ramsey multiplicity M(G;n) of a graph G is the minimum number of monochromatic copies of G over all 2‐colorings of the edges of the complete graph K_n. For a graph G with a automorphisms, ν vertices, and E edges, it is natural to define the Ramsey multiplicity constant C(G) to be , which is the limit of the fraction of the total number of copies of G which must be monochromatic in a 2‐coloring of the edges of K_n. In 1980, Burr and Rosta showed that 0 ≥ C(G) ≤ 2^1?E for all graphs G, and conjectured that this upper bound is tight. Counterexamples of Burr and Rosta's conjecture were first found by Sidorenko and Thomason independently. Later, Clark proved that there are graphs G with E edges and 2^E?1C(G) arbitrarily small. We prove that for each positive integer E, there is a graph G with E edges and C(G) ≤ E^{?E/2 + o(E)}. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 89–98, 2008     

On conditional edge-connectivity of graphs

1. IntroductionIn this paper, a graph G ~ (V,E) always means a simple graph (without loops andmultiple edges) with the vertex-set V and the edge-set E. We follow [1] for graph-theoreticalterllilnology and notation not defined here.It is well known that when the underlying topology of a computer interconnectionnetwork is modeled by a graph G, the edge-connectivity A(G) of G is an important measurefor fault-tolerance of the network. However, it has many deficiencies (see [2]). MotiVatedby t…     

An application of the regularity lemma in generalized Ramsey theory

Given graphs G and H, an edge coloring of G is called an (H,q)‐coloring if the edges of every copy of H ? G together receive at least q colors. Let r(G,H,q) denote the minimum number of colors in a (H,q)‐coloring of G. In 9 Erd?s and Gyárfás studied r(K_n,K_p,q) if p and q are fixed and n tends to infinity. They determined for every fixed p the smallest q (denoted by q_lin) for which r(K_n,K_p,q) is linear in n and the smallest q (denoted by q_quad) for which r(K_n,K_p,q) is quadratic in n. They raised the problem of determining the smallest q for which we have . In this paper by using the Regularity Lemma we show that if , then we have . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 39–49, 2003     

On the centralizer ofK in the universal enveloping algebra of SO(n,1) and SU(n,1)

LetG _o be a non compact real semisimple Lie group with finite center, and letU U(g) ^K denote the centralizer inU U(g) of a maximal compact subgroupK _o ofG _o. To study the algebraU U(g) ^K , B. Kostant suggested to consider the projection mapP:U U(g)→U(k)⊗U(a), associated to an Iwasawa decompositionG _o=K _o A _o N _o ofG _o, adapted toK _o. WhenP is restricted toU U(g) ^K J. Lepowsky showed thatP becomes an injective anti-homomorphism ofU U(g) ^K intoU(k) ^M ⊗U(a). HereU(k) ^M denotes the centralizer ofM _o inU(k),M _o being the centralizer ofA _o inK _o. To pursue this idea further it is necessary to have a good characterization of the image ofU U(g) ^K inU(k)^M×U(a). In this paper we describe such image whenG _o=SO(n,1)_e or SU(n,1). This is acomplished by establishing a (minimal) set of equations satisfied by the elements in the image ofU U(g) ^K , and then proving that they are enough to characterize such image. These equations are derived on one hand from the intertwining relations among the principal series representations ofG _o given by the Kunze-Stein interwining operators, and on the other hand from certain imbeddings among Verma modules. This approach should prove to be useful to attack the general case. Supported in part by Fundación Antorchas     

Some results on the achromatic number

Let G be a simple graph. The achromatic number ψ(G) is the largest number of colors possible in a proper vertex coloring of G in which each pair of colors is adjacent somewhere in G. For any positive integer m, let q(m) be the largest integer k such that ≤ m. We show that the problem of determining the achromatic number of a tree is NP-hard. We further prove that almost all trees T satisfy ψ (T) = q(m), where m is the number of edges in T. Lastly, for fixed d and ϵ > 0, we show that there is an integer N₀ = N₀(d, ϵ) such that if G is a graph with maximum degree at most d, and m ≥ N₀ edges, then (1 - ϵ)q(m) ≤ ψ (G) ≤ q(m). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 129–136, 1997     

Distortion Properties of Holomorphic Functions of Several Complex Variables

Let Q(D) be a class of functions q, q(0) = 0, |q(z)| < 1 holomorphic in the Reinhardt domain D ? C ⁿ, a and b — arbitrary fixed numbers satisfying the condition — 1 ≤ b < a ≤ 1. ??(a, b; D) — the class of functions p such that p ? ??(a, b; D) iff for some q ? Q(D) and every z ? D. S*(a, b; D) — the class of functions f such that f ? S*(a, g; D) iff S^c(a, b; D) — the class of functions q such that q ? S^c(a, b; D) iff , where p ε ??(a, b; D) and K is an operator of the form for z=z₁,z₂,…z_n. The author obtains sharp bounds on |p(z)|, f(z)| g(z)| as well as sharp coefficient inequalities for functions in ??(a, b; D), S*(a, b; D) and S^c(a, b; D).     

The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

The minimum degree of Ramsey‐minimal graphs

We write H → G if every 2‐coloring of the edges of graph H contains a monochromatic copy of graph G. A graph H is G‐minimal if H → G, but for every proper subgraph H′ of H, H′ ? G. We define s(G) to be the minimum s such that there exists a G‐minimal graph with a vertex of degree s. We prove that s(K_k) = (k ? 1)² and s(K_a,b) = 2 min(a,b) ? 1. We also pose several related open problems. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 167–177, 2007     

Graphs with unavoidable subgraphs with large degrees

Let ??(n, m) denote the class of simple graphs on n vertices and m edges and let G ∈ ?? (n, m). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a K_{k + 1} in terms of the number of edges in G. In this paper we prove that, for m = αn², α > (k - 1)/2k, G contains a K_{k + 1}, each vertex of which has degree at least f(α)n and determine the best possible f(α). For m = ?n²/4? + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = αn², α > 0 we establish that G contains a subgraph H with δ(H) ≥ f(α, n) and determine the best possible value of f(α, n).     

A note on a conjecture about cycles with many incident chords

Given positive integers n and k, let g_k(n) denote the maximum number of edges of a graph on n vertices that does not contain a cycle with k chords incident to a vertex on the cycle. Bollobás conjectured as an exercise in [2, p. 398, Problem 13] that there exists a function n(k) such that g_k(n) = (k + 1)n ? (k + 1)² for all n ≥ n(k). Using an old result of Bondy [ 3 ], we prove the conjecture, showing that n(k) ≤ 3 k + 3. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 180–182, 2004     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Large Monotone Paths in Graphs with Bounded Degree

 We prove that for every ε>0 and positive integer r, there exists Δ₀=Δ₀(ε) such that if Δ>Δ₀ and n>n(Δ,ε,r) then there exists a packing of K _n with ⌊(n−1)/Δ⌋ graphs, each having maximum degree at most Δ and girth at least r, where at most εn ² edges are unpacked. This result is used to prove the following: Let f be an assignment of real numbers to the edges of a graph G. Let α(G,f) denote the maximum length of a monotone simple path of G with respect to f. Let α(G) be the minimum of α(G,f), ranging over all possible assignments. Now let α_Δ be the maximum of α(G) ranging over all graphs with maximum degree at most Δ. We prove that Δ+1≥α_Δ≥Δ(1−o(1)). This extends some results of Graham and Kleitman [6] and of Calderbank et al. [4] who considered α(K _n ). Received: March 15, 1999?Final version received: October 22, 1999     

Large Kr‐free subgraphs in Ks‐free graphs and some other Ramsey‐type problems

In this paper we present three Ramsey‐type results, which we derive from a simple and yet powerful lemma, proved using probabilistic arguments. Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph K_s on s vertices. More than 40 years ago Erd?s and Rogers posed the problem of estimating the maximum size of a subset of G without a copy of the complete graph K_r. Our first result provides a new lower bound for this problem, which improves previous results of various researchers. It also allows us to solve some special cases of a closely related question posed by Erd?s. For two graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any red‐blue coloring of the edges of the complete graph K_N, contains either a red copy of G or a blue copy of H. The book with n pages is the graph B_n consisting of n triangles sharing one edge. Here we study the book‐complete graph Ramsey numbers and show that R(B_n, K_n) ≤ O(n³/log^3/2n), improving the bound of Li and Rousseau. Finally, motivated by a question of Erd?s, Hajnal, Simonovits, Sós, and Szemerédi, we obtain for all 0 < δ < 2/3 an estimate on the number of edges in a K₄‐free graph of order n which has no independent set of size n^1‐δ. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

On three zero-sum Ramsey-type problems

For a graph G whose number of edges is divisible by k, let R(G,Z_k) denote the minimum integer r such that for every function f: E(K_r) ? Z_k there is a copy G¹ of G in K_r so that Σe∈E(G¹) f(e) = 0 (in Z_k). We prove that for every integer k₁ R(K_n, Z_k) ≤ n + O(k³ log k) provided n is sufficiently large as a function of k and k divides (). If, in addition, k is an odd prime-power then R(K_n, Z_k) ≤ n + 2k - 2 and this is tight if k is a prime that divides n. A related result is obtained for hypergraphs. It is further shown that for every graph G on n vertices with an even number of edges R(G,Z₂) ≤ n + 2. This estimate is sharp. © 1993 John Wiley & Sons, Inc.     

Complete subgraphs with large degree sums

Let t(n, k) denote the Turán number—the maximum number of edges in a graph on n vertices that does not contain a complete graph K_k+1. It is shown that if G is a graph on n vertices with n ≥ k²(k – 1)/4 and m < t(n, k) edges, then G contains a complete subgraph K_k such that the sum of the degrees of the vertices is at least 2km/n. This result is sharp in an asymptotic sense in that the sum of the degrees of the vertices of K_k is not in general larger, and if the number of edges in G is at most t(n, k) – ? (for an appropriate ?), then the conclusion is not in general true. © 1992 John Wiley & Sons, Inc.     

A constructive approach for the lower bounds on the Ramsey numbers R (s,t)

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K_k, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some K_k?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004