The Ramsey numbers for disjoint unions of trees

For given graphs G and H, the Ramsey numberR(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper, we investigate the Ramsey number R(∪G,H), where G is a tree and H is a wheel W_m or a complete graph K_m. We show that if n?3, then R(kS_n,W₄)=(k+1)n for k?2, even n and R(kS_n,W₄)=(k+1)n-1 for k?1 and odd n. We also show that .     

Multicolor Ramsey numbers involving graphs with long suspended paths

Let G₁,…,G_c be graphs and let H be a connected graph. Let H_n be a graph on n points which is homeomorphic to H. It is proved that if n is large enough, the Ramsey number r(G₁,…,G_c,H_n) has the form (X?1)(n?1)+T. Here X and T are two Ramsey-type functons involving G₁,…,G_c only. The properties of these functions are studied, leading to explicit evaluations in a number of cases.     

Some connected ramsey numbers

A graph G is co-connected if both G and its complement ? are connected and nontrivial. For two graphs A and B, the connected Ramsey number r_c(A, B) is the smallest integer n such that there exists a co-connected graph of order n, and if G is a co-connected graph on at least n vertices, then A ? G or B ? ?. If neither A or B contains a bridge, then it is known that r_c(A, B) = r(A, B), where r(A, B) denotes the usual Ramsey number of A and B. In this paper r_c(A, B) is calculated for some pairs (A, B) when r(A, B) is known and at least one of the graphs A or B has a bridge. In particular, r_c(A, B) is calculated for A a path and B either a cycle, star, or complete graph, and for A a star and B a complete graph.     

Star-critical Ramsey numbers

The graph Ramsey numberR(G,H) is the smallest integer r such that every 2-coloring of the edges of K_r contains either a red copy of G or a blue copy of H. We find the largest star that can be removed from K_r such that the underlying graph is still forced to have a red G or a blue H. Thus, we introduce the star-critical Ramsey numberr_∗(G,H) as the smallest integer k such that every 2-coloring of the edges of K_r−K_1,r−1−k contains either a red copy of G or a blue copy of H. We find the star-critical Ramsey number for trees versus complete graphs, multiple copies of K₂ and K₃, and paths versus a 4-cycle. In addition to finding the star-critical Ramsey numbers, the critical graphs are classified for R(T_n,K_m), R(nK₂,mK₂) and R(P_n,C₄).     

Ramsey-goodness—and otherwise

A celebrated result of Chvátal, Rödl, Szemerédi and Trotter states (in slightly weakened form) that, for every natural number Δ, there is a constant r _Δ such that, for any connected n-vertex graph G with maximum degree Δ, the Ramsey number R(G,G) is at most r _Δ n, provided n is sufficiently large. In 1987, Burr made a strong conjecture implying that one may take r _Δ = Δ. However, Graham, Rödl and Ruciński showed, by taking G to be a suitable expander graph, that necessarily r _Δ > 2 ^cΔ for some constant c>0. We show that the use of expanders is essential: if we impose the additional restriction that the bandwidth of G be at most some function β(n)=o(n), then R(G,G)≤(2χ(G)+4)n≤(2Δ+6)n, i.e., r _Δ =2Δ+6 suffices. On the other hand, we show that Burr’s conjecture itself fails even for P _n ^k , the kth power of a path P _n . Brandt showed that for any c, if Δ is sufficiently large, there are connected n-vertex graphs G with Δ(G)≤Δ but R(G,K ₃) > cn. We show that, given Δ and H, there are β>0 and n ₀ such that, if G is a connected graph on n≥n ₀ vertices with maximum degree at most Δ and bandwidth at most β _n , then we have R(G,H)=(χ(H)?1)(n?1)+σ(H), where σ(H) is the smallest size of any part in any χ(H)-partition of H. We also show that the same conclusion holds without any restriction on the maximum degree of G if the bandwidth of G is at most ?(H) log n=log logn.     

Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs

For a finite simple edge-colored connected graph G (the coloring may not be proper), a rainbow path in G is a path without two edges colored the same; G is rainbow connected if for any two vertices of G, there is a rainbow path connecting them. Rainbow connection number, rc(G), of G is the minimum number of colors needed to color its edges such that G is rainbow connected. Chakraborty et al. (2011) [5] proved that computing rc(G) is NP-hard and deciding if rc(G)=2 is NP-complete. When edges of G are colored with fixed number k of colors, Kratochvil [6] proposed a question: what is the complexity of deciding whether G is rainbow connected? is this an FPT problem? In this paper, we prove that any maximal outerplanar graph is k rainbow connected for suitably large k and can be given a rainbow coloring in polynomial time.     

The multi‐color Ramsey number of an odd cycle

Let r_k(G) be the k‐color Ramsey number of a graph G. It is shown that for k?2 and that r_k(C_{2m+ 1})?(c^kk!)^1/m if the Ramsey graphs of r_k(C_{2m+ 1}) are not far away from being regular. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 324–328, 2009     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

On extremal k-outconnected graphs

Let G be a minimally k-connected graph with n nodes and m edges. Mader proved that if n?3k-2 then m?k(n-k), and for n?3k-1 an equality is possible if, and only if, G is the complete bipartite graph K_k,n-k. Cai proved that if n?3k-2 then m?⌊(n+k)²/8⌋, and listed the cases when this bound is tight.In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.     

Bipartite rainbow numbers of matchings

Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph K_m,n. Erd?s, Simonovits and Sós showed that rb(K_n,K₃)=n. In 2004, Schiermeyer determined the rainbow numbers rb(K_n,K_k) for all n≥k≥4, and the rainbow numbers rb(K_n,kK₂) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(K_m,n,kK₂) for all k≥1.     

The Ramsey numbers for disjoint unions of graphs

For given graphs G and H, the Ramsey number R(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper we investigate the Ramsey number of a disjoint union of graphs . For any natural integer k, we contain a general upper bound, R(kG,H)?R(G,H)+(k-1)|V(G)|. We also show that if m=2n-4, 2n-8 or 2n-6, then R(kS_n,W_m)=R(S_n,W_m)+(k-1)n. Furthermore, if |G_i|>(|G_i|-|G_i+1|)(χ(H)-1) and R(G_i,H)=(χ(H)-1)(|G_i|-1)+1, for each i, then .     

On a property of minimal triangulations

A graph H has the property MT, if for all graphs G, G is H-free if and only if every minimal (chordal) triangulation of G is H-free. We show that a graph H satisfies property MT if and only if H is edgeless, H is connected and is an induced subgraph of P₅, or H has two connected components and is an induced subgraph of 2P₃.This completes the results of Parra and Scheffler, who have shown that MT holds for H=P_k, the path on k vertices, if and only if k?5 [A. Parra, P. Scheffler, Characterizations and algorithmic applications of chordal graph embeddings, Discrete Applied Mathematics 79 (1997) 171-188], and of Meister, who proved that MT holds for ?P₂, ? copies of a P₂, if and only if ??2 [D. Meister, A complete characterisation of minimal triangulations of 2K₂-free graphs, Discrete Mathematics 306 (2006) 3327-3333].     

The equivariant topology of stable Kneser graphs

The stable Kneser graph SG_n,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K₂,SG_n,k)?Sk. The dihedral group D2m acts canonically on SG_n,k, the group C₂ with 2 elements acts on K₂. We almost determine the (C₂×D2m)-homotopy type of Hom(K₂,SG_n,k) and use this to prove the following results.The graphs SG_2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG_2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SG_n,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SG_n,k,G) is (r−1)-connected and χ(G)<r+k+2.     

The Ramsey number of paths with respect to wheels

For graphs G and H, the Ramsey numberR(G,H) is the smallest positive integer n such that every graph F of order n contains G or the complement of F contains H. For the path P_n and the wheel W_m, it is proved that R(P_n,W_m)=2n-1 if m is even, m?4, and n?(m/2)(m-2), and R(P_n,W_m)=3n-2 if m is odd, m?5, and n?(m-1/2)(m-3).     

Edge-deletable IM-extendable graphs with minimum number of edges

A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every F⊆E(G) with |F|=k, G−F is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either G≅K_k+2,k+2, or k=4r−2 for some integer r≥3 and G≅C₅[N_2r], where N_2r is the empty graph on 2r vertices and C₅[N_2r] is the graph obtained from C₅ by replacing each vertex with a graph isomorphic to N_2r.     

On two problems in graph Ramsey theory

We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every two-coloring of the edges of the complete graph K _N contains a monochromatic copy of H. A famous result of Chváatal, Rödl, Szemerédi and Trotter states that there exists a constant c(Δ) such that r(H) ≤ c(Δ)n for every graph H with n vertices and maximum degree Δ. The important open question is to determine the constant c(Δ). The best results, both due to Graham, Rödl and Ruciński, state that there are positive constants c and c′ such that $2^{c'\Delta } \leqslant c(\Delta ) \leqslant ^{c\Delta \log ^2 \Delta }$ . We improve this upper bound, showing that there is a constant c for which c(Δ) ≤ 2 ^cΔlogΔ . The induced Ramsey number r _ind (H) of a graph H is the least positive integer N for which there exists a graph G on N vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of H. Erd?s conjectured the existence of a constant c such that, for any graph H on n vertices, r _ind (H) ≤ 2 ^cnlogn . We move a step closer to proving this conjecture, showing that r _ind (H) ≤ 2 ^cnlogn . This improves upon an earlier result of Kohayakawa, Prömel and Rödl by a factor of logn in the exponent.     

On Petersen's graph theorem

In this paper we prove the following: let G be a graph with e_G edges, which is (k ? 1)-edge- connected, and with all valences ?k. Let 1?r?k be an integer, then G contains a spanning subgraph H, so that all valences in H are ?r, with no more than ?re_G?k? edges. The proof is based on a useful extension of Tutte's factor theorem [4,5], due to Lovász [3]. For other extensions of Petersen's theorem, see [6,7,8].     

Some Asymptotic ith Ramsey numbers

Let G be a graph with chromatic number χ(G) and let t(G) be the minimum number of vertices in any color class among all χ(G)-vertex colorings of G. Let H′ be a connected graph and let H be a graph obtained by subdividing (adding extra vertices to) a fixed edge of H′. It is proved that if the order of H is sufficiently large, the ith Ramsey number r_i(G, H) equals $\text{[}\text{((χ(G)?1)(|}\text{H}\text{|?1)+t(G)?1)}\text{i}\text{]+1}$.     

Tension polynomials of graphs

The tension polynomial F_G(k) of a graph G, evaluating the number of nowhere‐zero ?_k‐tensions in G, is the nontrivial divisor of the chromatic polynomial χ_G(k) of G, in that χ_G(k) = k^c(G)F_G(k), where c(G) denotes the number of components of G. We introduce the integral tension polynomial I_G(k), which evaluates the number of nowhere‐zero integral tensions in G with absolute values smaller than k. We show that 2^r(G)F_G(k)≥I_G(k)≥ (r(G)+1)F_G(k), where r(G)=|V(G)|?c(G), and, for every k>1, F_G(k+1)≥ F_G(k)˙k / (k?1) and I_G(k+1)≥I_G(k)˙k/(k?1). © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 137–146, 2002     

The Connected Monophonic Number of a Graph

For a connected graph G = (V, E) of order at least two, a chord of a path P is an edge joining two non-adjacent vertices of P. A path P is called a monophonic path if it is a chordless path. A set S of vertices of G is a monophonic set of G if each vertex v of G lies on an x ? y monophonic path for some elements x and y in S. The minimum cardinality of a monophonic set of G is defined as the monophonic number of G, denoted by m(G). A connected monophonic set of G is a monophonic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected monophonic set of G is the connected monophonic number of G and is denoted by m _c (G). We determine bounds for it and characterize graphs which realize these bounds. For any two vertices u and v in G, the monophonic distance d _m (u, v) from u to v is defined as the length of a longest u ? v monophonic path in G. The monophonic eccentricity e _m (v) of a vertex v in G is the maximum monophonic distance from v to a vertex of G. The monophonic radius rad _m G of G is the minimum monophonic eccentricity among the vertices of G, while the monophonic diameter diam _m G of G is the maximum monophonic eccentricity among the vertices of G. It is shown that for positive integers r, d and n ≥ 5 with r <  d, there exists a connected graph G with rad _m G =  r, diam _m G =  d and m _c (G) =  n. Also, if a,b and p are positive integers such that 2 ≤  a <  b ≤  p, then there exists a connected graph G of order p, m(G) =  a and m _c (G) =  b.