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].     

On the Multichromatic Number of s‐Stable Kneser Graphs

For positive integers n and s, a subset [n] is s‐stable if for distinct . The s‐stable r‐uniform Kneser hypergraph is the r‐uniform hypergraph that has the collection of all s‐stable k‐element subsets of [n] as vertex set and whose edges are formed by the r‐tuples of disjoint s‐stable k‐element subsets of [n]. Meunier ( 21 ) conjectured that for positive integers with , and , the chromatic number of s‐stable r ‐uniform Kneser hypergraphs is equal to . It is a generalized version of the conjecture proposed by Alon et al. ( 1 ). Alon et al. ( 1 ) confirmed Meunier's conjecture for with arbitrary positive integer q. Lin et al. ( 17 ) studied the kth chromatic number of the Mycielskian of the ordinary Kneser graphs for . They conjectured that for . The case was proved by Mycielski ( 22 ). Lin et al. ( 17 ) confirmed their conjecture for , or when n is a multiple of k or . In this paper, we investigate the multichromatic number of the usual s ‐stable Kneser graphs . With the help of Fan's (1952) combinatorial lemma, we show that Meunier's conjecture is true for r is a power of 2 and s is a multiple of r, and Lin‐Liu‐Zhu's conjecture is true for .     

Non-cover generalized Mycielski, Kneser, and Schrijver graphs

A graph is said to be a cover graph if it is the underlying graph of the Hasse diagram of a finite partially ordered set. We prove that the generalized Mycielski graphs M_m(C_2t+1) of an odd cycle, Kneser graphs KG(n,k), and Schrijver graphs SG(n,k) are not cover graphs when m?0,t?1, k?1, and n?2k+2. These results have consequences in circular chromatic number.     

On the locating chromatic number of Kneser graphs

Let c be a proper k-coloring of a connected graph G and Π=(C₁,C₂,…,C_k) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple c_Π(v):=(d(v,C₁),d(v,C₂),…,d(v,C_k)), where d(v,C_i)=min{d(v,x)|x∈C_i},1≤i≤k. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χ_L(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χ_L(KG(n,2))=n−1 for all n≥5. Then, we prove that χ_L(KG(n,k))≤n−1, when n≥k². Moreover, we present some bounds for the locating chromatic number of odd graphs.     

A dimension inequality for Cohen-Macaulay rings

The recent work of Kurano and Roberts on Serre's positivity conjecture suggests the following dimension inequality: for prime ideals and in a local, Cohen-Macaulay ring such that we have . We establish this dimension inequality for excellent, local, Cohen-Macaulay rings which contain a field, for certain low-dimensional cases and when is regular.

     

Flow hypergraph reducibility

Reducible flowgraphs were first defined by Allen in terms of intervals; another definition based on two flowgraph transformations was presented by Hecht and Ullman. In this paper, we extend the notion of reducibility to directed hypergraphs, proving that the interval and the transformation approaches preserve the equivalence when applied to this family.     

Local coloring of Kneser graphs

A local coloring of a graph G is a function c:V(G)→N having the property that for each set S⊆V(G) with 2≤|S|≤3, there exist vertices u,v∈S such that |c(u)−c(v)|≥m_S, where m_S is the number of edges of the induced subgraph 〈S〉. The maximum color assigned by a local coloring c to a vertex of G is called the value of c and is denoted by χ_?(c). The local chromatic number of G is χ_?(G)=min{χ_?(c)}, where the minimum is taken over all local colorings c of G. The local coloring of graphs was introduced by Chartrand et al. [G. Chartrand, E. Salehi, P. Zhang, On local colorings of graphs, Congressus Numerantium 163 (2003) 207-221]. In this paper the local coloring of Kneser graphs is studied and the local chromatic number of the Kneser graph K(n,k) for some values of n and k is determined.     

Hom complexes and hypergraph colorings

Babson and Kozlov (2006) [2] studied Hom-complexes of graphs with a focus on graph colorings. In this paper, we generalize Hom-complexes to r-uniform hypergraphs (with multiplicities) and study them mainly in connection with hypergraph colorings. We reinterpret a result of Alon, Frankl and Lovász (1986) [1] by Hom-complexes and show a hierarchy of known lower bounds for the chromatic numbers of r-uniform hypergraphs (with multiplicities) using Hom-complexes.     

On nonexistence of Kneser solutions of third-order neutral delay differential equations

The aim of this paper is to complement existing oscillation results for third-order neutral delay differential equations by establishing sufficient conditions for nonexistence of so-called Kneser solutions. Combining newly obtained results with existing ones, we attain oscillation of all solutions of the studied equations.     

Quasi-random 2- colorings of point sets

Given an arbitrary set of N points on the plane, one can two-color the points red and blue in such a way that the difference of the numbers of red and blue points in any half-plane has absolute value less than N^1/4(log N)⁴. This is essentially best possible.