共查询到20条相似文献,搜索用时 46 毫秒
1.
Sarah Crown 《Journal of Combinatorial Theory, Series A》2009,116(3):595-612
Let G be a simple graph on n vertices, and let χG(λ) denote the chromatic polynomial of G. In this paper, we define the cyclic coloring complex, Δ(G), and determine the dimensions of its homology groups for simple graphs. In particular, we show that if G has r connected components, the dimension of (n−3)rd homology group of Δ(G) is equal to (n−(r+1)) plus , where is the rth derivative of χG(λ). We also define a complex ΔC(G), whose r-faces consist of all ordered set partitions [B1,…,Br+2] where none of the Bi contain an edge of G and where 1∈B1. We compute the dimensions of the homology groups of this complex, and as a result, obtain the dimensions of the multilinear parts of the cyclic homology groups of C[x1,…,xn]/{xixj|ij is an edge of G}. We show that when G is a connected graph, the homology of ΔC(G) has nonzero homology only in dimension n−2, and the dimension of this homology group is . In this case, we provide a bijection between a set of homology representatives of ΔC(G) and the acyclic orientations of G with a unique source at v, a vertex of G. 相似文献
2.
Sarah Crown Rundell 《Journal of Combinatorial Theory, Series A》2012,119(5):1095-1109
In this paper, we study the homology of the coloring complex and the cyclic coloring complex of a complete k-uniform hypergraph. We show that the coloring complex of a complete k-uniform hypergraph is shellable, and we determine the rank of its unique nontrivial homology group in terms of its chromatic polynomial. We also show that the dimension of the homology group of the cyclic coloring complex of a complete k-uniform hypergraph is given by a binomial coefficient. Further, we discuss a complex whose r-faces consist of all ordered set partitions where none of the contain a hyperedge of the complete k-uniform hypergraph H and where . It is shown that the dimensions of the homology groups of this complex are given by binomial coefficients. As a consequence, this result gives the dimensions of the multilinear parts of the cyclic homology groups of . 相似文献
3.
Steingrimsson’s coloring complex and Jonsson’s unipolar complex are interpreted in terms of hyperplane arrangements. This
viewpoint leads to short proofs that all coloring complexes and a large class of unipolar complexes have convex ear decompositions.
These convex ear decompositions impose strong new restrictions on the chromatic polynomials of all finite graphs. Similar
results are obtained for characteristic polynomials of submatroids of type ℬ
n
arrangements.
The first author was supported by NSF grant DMS-0500638. The second author was supported by NSF grant DMS-0245623. 相似文献
4.
5.
We study Beck-like coloring of partially ordered sets (posets) with a least element 0. To any poset P with 0 we assign a graph (called a zero-divisor graph) whose vertices are labelled by the elements of P with two vertices x,y adjacent if 0 is the only element lying below x and y. We prove that for such graphs, the chromatic number and the clique number coincide. Also, we give a condition under which posets are not finitely colorable. 相似文献
6.
7.
8.
In this note, we determine the maximum number of edges of a k-uniform hypergraph, k≥3, with a unique perfect matching. This settles a conjecture proposed by Snevily. 相似文献
10.
The upper chromatic number of a hypergraph H=(X,E) is the maximum number k for which there exists a partition of X into non-empty subsets X=X1∪X2∪?∪Xk such that for each edge at least two vertices lie in one of the partite sets. We prove that for every n?3 there exists a 3-uniform hypergraph with n vertices, upper chromatic number 2 and ⌈n(n-2)/3⌉ edges which implies that a corresponding bound proved in [K. Diao, P. Zhao, H. Zhou, About the upper chromatic number of a co-hypergraph, Discrete Math. 220 (2000) 67-73] is best-possible. 相似文献
11.
Carsten Thomassen 《Discrete Mathematics》2006,306(23):3145-3153
We prove that, for every fixed surface S, there exists a largest positive constant c such that every 5-colorable graph with n vertices on S has at least c·2n distinct 5-colorings. This is best possible in the sense that, for each sufficiently large natural number n, there is a graph with n vertices on S that has precisely c·2n distinct 5-colorings. For the sphere the constant c is , and for each other surface, it is a finite problem to determine c. There is an analogous result for k-colorings for each natural number k>5. 相似文献
12.
Stephen B. Seidman 《Mathematical Social Sciences》1981,1(4):381-396
During recent years, much attention has been paid by anthropologists and sociologists to the analysis of social networks. These networks arise from dyadic relationships such as kinship or friendship and they have been studied using techniques derived from graph theory. Although the study of such networks can cast much light on the social structure of a population, many important aspects of this structure cannot be addressed using dyadic relationships alone. For example, group membership gives rise to natural non-dyadic relationships which will be distorted if they are forced into a dyadic mold. The purpose of this paper is to propose an analytical scheme which will permit the study of structure induced by non-dyadic relationships. The concepts used derive from the theory of hypergraphs, and it is shown that these concepts permit a wide variety of structural questions to be posed. 相似文献
13.
14.
15.
图的正常三着色的最大方法数 总被引:1,自引:0,他引:1
令F_(v,e)表示所有简单无向(v,e)-图的全体所成的集合,f(v,e,λ)=max{P(G,λ);G∈F_(v,e)}.本文改进了文献[1]中给出的f(v,e,3)的上界,并指出[1]中的猜想的充分性是不成立的. 相似文献
16.
17.
Let P(G,λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H,λ)=P(G,λ) implies H is isomorphic to G. For integers k≥0, t≥2, denote by K((t−1)×p,p+k) the complete t-partite graph that has t−1 partite sets of size p and one partite set of size p+k. Let K(s,t,p,k) be the set of graphs obtained from K((t−1)×p,p+k) by adding a set S of s edges to the partite set of size p+k such that 〈S〉 is bipartite. If s=1, denote the only graph in K(s,t,p,k) by K+((t−1)×p,p+k). In this paper, we shall prove that for k=0,1 and p+k≥s+2, each graph G∈K(s,t,p,k) is chromatically unique if and only if 〈S〉 is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph K+((t−1)×p,p+k) is chromatically unique for k=0,1 and p+k≥3. 相似文献
18.
Khaled M. Elbassioni 《Discrete Applied Mathematics》2008,156(11):2109-2123
In 1994 Fredman and Khachiyan established the remarkable result that the duality of a pair of monotone Boolean functions, in disjunctive normal forms, can be tested in quasi-polynomial time, thus putting the problem, most likely, somewhere between polynomiality and coNP-completeness. We strengthen this result by showing that the duality testing problem can in fact be solved in polylogarithmic time using a quasi-polynomial number of processors (in the PRAM model). While our decomposition technique can be thought of as a generalization of that of Fredman and Khachiyan, it yields stronger bounds on the sequential complexity of the problem in the case when the sizes of f and g are significantly different, and also allows for generating all minimal transversals of a given hypergraph using only polynomial space. 相似文献
19.
S. Nicoloso 《Discrete Mathematics》2004,280(1-3):251-257
The SUM COLORING problem consists of assigning a color c(vi)Z+ to each vertex viV of a graph G=(V,E) so that adjacent nodes have different colors and the sum of the c(vi)'s over all vertices viV is minimized. In this note we prove that the number of colors required to attain a minimum valued sum on arbitrary interval graphs does not exceed min{n;2χ(G)−1}. Examples from the papers [Discrete Math. 174 (1999) 125; Algorithmica 23 (1999) 109] show that the bound is tight. 相似文献