共查询到20条相似文献,搜索用时 15 毫秒
1.
Carsten Schultz 《Journal of Combinatorial Theory, Series A》2011,118(8):2291-2318
The stable Kneser graph SGn,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(K2,SGn,k)?Sk. The dihedral group D2m acts canonically on SGn,k, the group C2 with 2 elements acts on K2. We almost determine the (C2×D2m)-homotopy type of Hom(K2,SGn,k) and use this to prove the following results.The graphs SG2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG2s,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 SGn,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SGn,k,G) is (r−1)-connected and χ(G)<r+k+2. 相似文献
2.
3.
A -coloring of a graph with colors is a proper coloring of using colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer for which has a -coloring using colors is the -chromatic number of . The -spectrum of a graph is the set of positive integers , for which has a -coloring using colors. A graph is -continuous if = the closed interval . In this paper, we obtain an upper bound for the -chromatic number of some families of Kneser graphs. In addition we establish that for the Kneser graph whenever . We also establish the -continuity of some families of regular graphs which include the family of odd graphs. 相似文献
4.
5.
6.
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)|≥mS, where mS 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. 相似文献
7.
Let
and
be two intersecting families of k-subsets of an n-element set. It is proven that |
| ≤ (k−1n−1) + (k−1n−1) holds for
, and equality holds only if there exist two points a, b such that {a, b} ∩ F ≠ for all F
. For
an example showing that in this case max |
| = (1−o(1))(kn) is given. This disproves an old conjecture of Erdös [7]. In the second part we deal with several generalizations of Kneser's conjecture. 相似文献
8.
We investigate the maximum number of edges in a bipartite subgraph of the Kneser graphK(n, r). The exact solution is given for eitherr arbitrary andn (4.3 + o(1))r, orr = 2 andn arbitrary. The problem is in connection with the study of the bipartite subgraph polytope of a graph.Research supported in part by the AKA Research Fund of the Hungarian Academy of Sciences 相似文献
9.
Yongzhu Chen 《Discrete Mathematics》2008,308(18):4276-4279
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]. 相似文献
10.
An edge-coloured graph G is a vertex set V(G) together with m edge sets distinguished by m colours. Let π be a permutation on {1,2,…,m}. We define a switching operation consisting of π acting on the edge colours similar to Seidel switching, to switching classes as studied by Babai and Cameron, and to the pushing operation studied by Klostermeyer and MacGillivray. An edge-coloured graph G is π-permutably homomorphic (respectively π-permutably isomorphic) to an edge-coloured graph H if some sequence of switches on G produces an edge-coloured graph homomorphic (respectively isomorphic) to H. We study the π-homomorphism and π-isomorphism operations, relating them to homomorphisms and isomorphisms of a constructed edge-coloured graph that we introduce called a colour switching graph. Finally, we identify those edge-coloured graphs H with the property that G is homomorphic to H if and only if any switch of G is homomorphic to H. It turns out that such an H is precisely a colour switching graph. As a corollary to our work, we settle an open problem of Klostermeyer and MacGillivray. 相似文献
11.
《Discrete Mathematics》2019,342(4):1017-1027
We study the independence number of a product of Kneser graph with itself, where we consider all four standard graph products. The cases of the direct, the lexicographic and the strong product of Kneser graphs are not difficult (the formula for is presented in this paper), while the case of the Cartesian product of Kneser graphs is much more involved. We establish a lower bound and an upper bound for the independence number of , which are asymptotically tending to and , respectively. The former is obtained by a construction, which differs from the standard diagonalization procedure, while for the upper bound the -independence number of Kneser graphs can be applied. We also establish some constructions in odd graphs , which give a lower bound for the 2-independence number of these graphs, and prove that two such constructions give the same lower bound as a previously known one. Finally, we consider the -stable Kneser graphs , derive a formula for their -independence number, and give the exact value of the independence number of the Cartesian square of . 相似文献
12.
Hossein Hajiabolhassan 《Discrete Applied Mathematics》2010,158(3):232-234
In this note, we prove that for any integer n≥3 the b-chromatic number of the Kneser graph KG(m,n) is greater than or equal to . This gives an affirmative answer to a conjecture of [6]. 相似文献
13.
A new coloring theorem of Kneser graphs 总被引:1,自引:0,他引:1
Peng-An Chen 《Journal of Combinatorial Theory, Series A》2011,118(3):1062-1071
In 1997, Johnson, Holroyd and Stahl conjectured that the circular chromatic number of the Kneser graphs KG(n,k) is equal to the chromatic number of these graphs. This was proved by Simonyi and Tardos (2006) [13] and independently by Meunier (2005) [10], if χ(KG(n,k)) is even. In this paper, we propose an alternative version of Kneser's coloring theorem to confirm the Johnson-Holroyd-Stahl conjecture. 相似文献
14.
15.
For a finite group G let Γ(G) be the (simple) graph defined on the elements of G with an edge between two (distinct) vertices if and only if they generate G. The chromatic number of Γ(G) is considered for various non-solvable groups G. 相似文献
16.
Robert F. Bailey José Cáceres Delia Garijo Antonio González Alberto Márquez Karen Meagher María Luz Puertas 《European Journal of Combinatorics》2013
A set of vertices S in a graph G is a resolving set for G if, for any two vertices u,v, there exists x∈S such that the distances d(u,x)≠d(v,x). In this paper, we consider the Johnson graphs J(n,k) and Kneser graphs K(n,k), and obtain various constructions of resolving sets for these graphs. As well as general constructions, we show that various interesting combinatorial objects can be used to obtain resolving sets in these graphs, including (for Johnson graphs) projective planes and symmetric designs, as well as (for Kneser graphs) partial geometries, Hadamard matrices, Steiner systems and toroidal grids. 相似文献
17.
《Discrete Mathematics》2022,345(7):112886
In this article we investigate a problem in graph theory, which has an equivalent reformulation in extremal set theory similar to the problems researched in “A general 2-part Erd?s-Ko-Rado theorem” by Gyula O.H. Katona, who proposed our problem as well. In the graph theoretic form we examine the clique number of the Xor product of two isomorphic Kneser graphs. Denote this number with . We give lower and upper bounds on , and we solve the problem up to a constant deviation depending only on k, and find the exact value for if N is large enough. Also we compute that is asymptotically equivalent to . 相似文献
18.
19.
Ali Behtoei Behnaz Omoomi 《Discrete Applied Mathematics》2011,159(18):2214-2221
Let c be a proper k-coloring of a connected graph G and Π=(C1,C2,…,Ck) 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,C1),d(v,C2),…,d(v,Ck)), where d(v,Ci)=min{d(v,x)|x∈Ci},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≥k2. Moreover, we present some bounds for the locating chromatic number of odd graphs. 相似文献
20.
A family of distance graphs whose structure is close to that of Kneser graphs is studied. New lower and upper bounds for the chromatic numbers of such graphs are obtained, and relations between these numbers are considered. The structure of certain important independent sets of the family of graphs under consideration is described, and the cardinalities of these sets are explicitly calculated. 相似文献