On the chromatic number of the general Kneser-graph

Given integers k, n, 2 < k < n, let us define a graph with vertex set V = {F ?{1, 2, …, n}: ∩F = k}, and (F, F') is an edge if |F ∩ F′| ≤ 1. We show that for n > n₀(k) the chromatic number of this graph is (k - 1)() + rs, where n = (k - 1)s + r, 0 ≤ r < k - 1.     

Diameters of uniform subset graphs

Let r,s be positive integers with r>s, k a nonnegative integer, and n=2r−s+k. A uniform subset graph G(n,r,s) is a graph with vertex set [n]^r and where two r-subsets A,B∈[n]^r are adjacent if and only if |A∩B|=s. Let denote the diameter of a graph G.In this paper, we prove the following results: (1) If k>0, then if r≥2s+k+2, 2 if k≥s and 2s≤r≤s+k, or k<s and s+k≤r≤2s, and 3 otherwise; (2) If k=0, then . This generalizes a result in [M. Valencia-Pabon, J.-C. Vera, On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383-385].     

Graphic sequences with a realization containing a generalized friendship graph

Gould, Jacobson and Lehel [R.J. Gould, M.S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi, et al. (Eds.), Combinatorics, Graph Theory and Algorithms, vol. I, New Issues Press, Kalamazoo, MI, 1999, pp. 451-460] considered a variation of the classical Turán-type extremal problems as follows: for any simple graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂+?+d_n≥σ(H,n) has a realization G containing H as a subgraph. Let F_t,r,k denote the generalized friendship graph on kt−kr+r vertices, that is, the graph of k copies of K_t meeting in a common r set, where K_t is the complete graph on t vertices and 0≤r≤t. In this paper, we determine σ(F_t,r,k,n) for k≥2, t≥3, 1≤r≤t−2 and n sufficiently large.     

On (s,t)-supereulerian graphs in locally highly connected graphs

Given two nonnegative integers s and t, a graph G is (s,t)-supereulerian if for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y|≤t, there is a spanning eulerian subgraph H of G that contains X and avoids Y. We prove that if G is connected and locally k-edge-connected, then G is (s,t)-supereulerian, for any pair of nonnegative integers s and t with s+t≤k−1. We further show that if s+t≤k and G is a connected, locally k-edge-connected graph, then for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y≤t, there is a spanning eulerian subgraph H that contains X and avoids Y, if and only if G−Y is not contractible to K₂ or to K_2,l with l odd.     

[r,s, t]-Colorings of Graph Products

Let G =  (V, E) be a graph with vertex set V and edge set E. Given non negative integers r, s and t, an [r, s, t]-coloring of a graph G is a proper total coloring where the neighboring elements of G (vertices and edges) receive colors with a certain difference r between colors of adjacent vertices, a difference s between colors of adjacent edges and a difference t between colors of a vertex and an incident edge. Thus [r, s, t]-colorings generalize the classical colorings of graphs and can have applications in different fields like scheduling, channel assignment problem, etc. The [r, s, t]-chromatic number χ _r,s,t (G) of G is the minimum k such that G admits an [r, s, t]-coloring. In our paper we propose several bounds for the [r, s, t]-chromatic number of the cartesian and direct products of some graphs.     

Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.     

Generalizing Pancyclic and <Emphasis Type="Italic">k</Emphasis>-Ordered Graphs

Given positive integers kmn, a graph G of order n is (k,m)-pancyclic if for any set of k vertices of G and any integer r with mrn, there is a cycle of length r containing the k vertices. Minimum degree conditions and minimum sum of degree conditions of nonadjacent vertices that imply a graph is (k,m)-pancylic are proved. If the additional property that the k vertices must appear on the cycle in a specified order is required, then the graph is said to be (k,m)-pancyclic ordered. Minimum degree conditions and minimum sum of degree conditions for nonadjacent vertices that imply a graph is (k,m)-pancylic ordered are also proved. Examples showing that these constraints are best possible are provided.Acknowledgments. The authors would like to thank the referees for their careful reading of the paper and their useful suggestions.Final version received: January 26, 2004     

Constructions of bi-regular cages

Given three positive integers r,m and g, one interesting question is the following: What is the minimum number of vertices that a graph with prescribed degree set {r,m}, 2≤r<m, and girth g can have? Such a graph is called a bi-regular cage or an ({r,m};g)-cage, and its minimum order is denoted by n({r,m};g). In this paper we provide new upper bounds on n({r,m};g) for some related values of r and m. Moreover, if r−1 is a prime power, we construct the following bi-regular cages: ({r,k(r−1)};g)-cages for g∈{5,7,11} and k≥2 even; and ({r,kr};6)-cages for k≥2 any integer. The latter cages are of order n({r,kr};6)=2(kr²−kr+1). Then this result supports the conjecture that n({r,m};6)=2(rm−m+1) for any r<m, posed by Yuansheng and Liang [Y. Yuansheng, W. Liang, The minimum number of vertices with girth 6 and degree set D={r,m}, Discrete Math. 269 (2003) 249-258]. We finalize giving the exact value n({3,3k};8), for k≥2.     

Path-path Ramsey-type numbers for the complete bipartite graph

For a fixed pair of integers r, s ≥ 2, all positive integers m and n are determined which have the property that if the edges of K_m,n (a complete bipartite graph with parts n and m) are colored with two colors, then there will always exist a path with r vertices in the first color or a path with s vertices in the second color.     

An Ore-type condition for arbitrarily vertex decomposable graphs

Let G be a graph of order n and r, 1≤r≤n, a fixed integer. G is said to be r-vertex decomposable if for each sequence (n₁,…,n_r) of positive integers such that n₁+?+n_r=n there exists a partition (V₁,…,V_r) of the vertex set of G such that for each i∈{1,…,r}, V_i induces a connected subgraph of G on n_i vertices. G is called arbitrarily vertex decomposable if it is r-vertex decomposable for each r∈{1,…,n}.In this paper we show that if G is a connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n−3, then G is arbitrarily vertex decomposable or isomorphic to one of two exceptional graphs. We also exhibit the integers r for which the graphs verifying the above degree-sum condition are not r-vertex decomposable.     

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.     

A multiply intersecting Erd?s-Ko-Rado theorem — The principal case

Let m(n,k,r,t) be the maximum size of satisfying |F₁∩?∩F_r|≥t for all F₁,…,F_r∈F. We prove that for every p∈(0,1) there is some r₀ such that, for all r>r₀ and all t with 1≤t≤⌊(p^1−r−p)/(1−p)⌋−r, there exists n₀ so that if n>n₀ and p=k/n, then . The upper bound for t is tight for fixed p and r.     

Hamiltonian Type Properties in Claw-Free $$P_5$$-Free Graphs

A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each integer r in the set \(\{ m, m + 1, \ldots , n \}\). This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree et al. in (Graphs Combin 20:291–310, 2004). The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. Broersma and Veldman showed in (Contemporary methods in graph theory, BI-Wiss.-Verlag, Mannheim, Wien, Zürich, pp 181–194, 1990) that any 2-connected claw-free \(P_5\)-free graph must be hamiltonian. In fact, every non-hamiltonian cycle in such a graph is either extendable or very dense. We show that any 2-connected claw-free \(P_5\)-free graph is (k, 3k)-pancyclic for each integer \(k \ge 2\). We also show that such a graph is (1, 5)-pancyclic. Examples are provided which show that these results are best possible. Each example we provide represents an infinite family of graphs.     

Disjoint chorded cycles in graphs

We propose the following conjecture to generalize results of Pósa and of Corrádi and Hajnal. Let r,s be nonnegative integers and let G be a graph with |V(G)|≥3r+4s and minimal degree δ(G)≥2r+3s. Then G contains a collection of r+s vertex disjoint cycles, s of them with a chord. We prove the conjecture for r=0,s=2 and for s=1. The corresponding extremal problem, to find the minimum number of edges in a graph on n vertices ensuring the existence of two vertex disjoint chorded cycles, is also settled.     

A contribution to the Zarankiewicz problem

Given positive integers let z(m,n,s,t) be the maximum number of ones in a (0,1) matrix of size m×n that does not contain an all ones submatrix of size s×t. We show that if s?2 and t?2, then for every k=0,…,s-2,

z(m,n,s,t)?(s-k-1)^1/tnm^1-1/t+kn+(t-1)m^1+k/t.     

On the diameter of generalized Kneser graphs

Let r, k be positive integers, s(<r), a nonnegative integer, and n=2r-s+k. The set of r-subsets of [n]={1,2,…,n} is denoted by [n]^r. The generalized Kneser graph K(n,r,s) is the graph whose vertex-set is [n]^r where two r-subsets A and B are joined by an edge if |A∩B|?s. This note determines the diameter of generalized Kneser graphs. More precisely, the diameter of K(n,r,s) is equal to , which generalizes a result of Valencia-Pabon and Vera [On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383-385].     

Determinantal varieties over truncated polynomial rings

We study components and dimensions of higher-order determinantal varieties obtained by considering generic m×n (m?n) matrices over rings of the form F[t]/(t^k), and for some fixed r, setting the coefficients of powers of t of all r×r minors to zero. These varieties can be interpreted as spaces of (k−1)th order jets over the classical determinantal varieties; a special case of these varieties first appeared in a problem in commuting matrices. We show that when r=m, the varieties are irreducible, but when r<m, these varieties are reducible. We show that when r=2<m (any k), there are exactly ⌊k/2⌋+1 components, which we determine explicitly, and for general r<m, we show there are at least ⌊k/2⌋+1 components. We also determine the components explicitly for k=2 and 3 for all values of r (for k=3 for all but finitely many pairs of (m,n)).     

Ramsey Numbers of Some Bipartite Graphs Versus Complete Graphs

The Ramsey number r(H, K _n ) is the smallest positive integer N such that every graph of order N contains either a copy of H or an independent set of size n. The Turán number ex(m, H) is the maximum number of edges in a graph of order m not containing a copy of H. We prove the following two results: (1) Let H be a graph obtained from a tree F of order t by adding a new vertex w and joining w to each vertex of F by a path of length k such that any two of these paths share only w. Then r(H,K_n) ￡ c_k,t [(n^1+1/k)/(ln^1/k n)]{r(H,K_n)\leq c_{k,t}\, {n^{1+1/k}\over \ln^{1/k} n}} , where c _k,t is a constant depending only on k and t. This generalizes some results in Li and Rousseau (J Graph Theory 23:413–420, 1996), Li and Zang (J Combin Optim 7:353–359, 2003), and Sudakov (Electron J Combin 9, N1, 4 pp, 2002). (2) Let H be a bipartite graph with ex(m, H) = O(m ^γ ), where 1 < γ < 2. Then r(H,K_n) ￡ c_H ([(n)/(lnn)])^1/(2-g){r(H,K_n)\leq c_H ({n\over \ln n})^{1/(2-\gamma)}}, where c _H is a constant depending only on H. This generalizes a result in Caro et al. (Discrete Math 220:51–56, 2000).     

Minimal Degree and (k, m)-Pancyclic Ordered Graphs

Given positive integers k m n, a graph G of order n is (k, m)-pancyclic ordered if for any set of k vertices of G and any integer r with m r n, there is a cycle of length r encountering the k vertices in a specified order. Minimum degree conditions that imply a graph of sufficiently large order n is (k, m)-pancylic ordered are proved. Examples showing that these constraints are best possible are also provided.     

Asymptotic enumeration of dense 0-1 matrices with specified line sums

Let s=(s₁,s₂,…,sm) and t=(t₁,t₂,…,tn) be vectors of non-negative integers with . Let B(s,t) be the number of m×n matrices over {0,1} with jth row sum equal to sj for 1?j?m and kth column sum equal to tk for 1?k?n. Equivalently, B(s,t) is the number of bipartite graphs with m vertices in one part with degrees given by s, and n vertices in the other part with degrees given by t. Most research on the asymptotics of B(s,t) has focused on the sparse case, where the best result is that of Greenhill, McKay and Wang (2006). In the case of dense matrices, the only precise result is for the case of equal row sums and equal column sums (Canfield and McKay, 2005). This paper extends the analytic methods used by the latter paper to the case where the row and column sums can vary within certain limits. Interestingly, the result can be expressed by the same formula which holds in the sparse case.