共查询到20条相似文献,搜索用时 78 毫秒
2.
3.
文中引入了P-置换图的概念.作为置换群的指标多项式和函数等价类配置多项式的推广形式分别定义了P-置换图的容量指标多项式与色权多项式,并给出了递归公式和相关定理,由此建立了计算P-置换图的色权多项式的一般方法和P-置换图的色轨道多项式的表达公式.Polya计数定理是这一公式当约束图是空图时的特例.最后给出了P-置换图的色权多项式的一些基本性质和两个计算实例. 相似文献
4.
本文利用色多项式的性质,讨论了具有色多项式∏i∑kui/k(k/ui-k)(λ)k的图的结构,给出了具有这种色多项式的全部色等价图. 相似文献
5.
文中引入了P-置换图的概念.作为置换群的指标多项式和函数等价类配置多项式的推广形式分别定义了P-置换图的容量指标多项式与色权多项式,并给出了递归公式和相关定理,由此建立了计算P-置换图的色权多项式的一般方法和P-置换图的色轨道多项式的表达公式.Pblya计数定理是这一公式当约束图是空图时的特例.最后给出了P-置换图的色权多项式的一些基本性质和两个计算实例. 相似文献
6.
本文给出下列图的色多项式的递推公式:删去图的一个二次或三次顶点;图的一边换成长为 k 的路;图 G 由 G_1和 G_2重迭一条路所组成,以及 Cm 多重图的边细分图的色多项式。 相似文献
7.
8.
9.
我们通过研究图的伴随多项式的因式分解,给出了证明非色唯一图的一种新方法,同时得到若干图簇的色等价图的结构定理. 相似文献
10.
G_(v_i)~*型图的伴随多项式的因式分解及其色性分析 总被引:1,自引:1,他引:0
任运平 《数学的实践与认识》2003,33(3):79-81
通过研究图的伴随多项式的因式分解 ,给出了证明非色唯一图的一种新的途径 ,并且得到了色等价图簇的结构特征 . 相似文献
11.
12.
It is known that the chromatic polynomial and flow polynomial of a graph are two important evaluations of its Tutte polynomial, both of which contain much information of the graph. Much research is done on graphs determined entirely by their chromatic polynomials and Tutte polynomials, respectively. Oxley asked which classes of graphs or matroids are determined by their chromatic and flow polynomials together. In this paper, we found several classes of graphs with this property. We first study which graphic parameters are determined by the flow polynomials. Then we study flow-unique graphs. Finally, we show that several classes of graphs, ladders, Möbius ladders and squares of n-cycle are determined by their chromatic polynomials and flow polynomials together. A direct consequence of our theorem is a result of de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomial, Graphs Comb. 20 (2004) 105-119] that these classes of graphs are Tutte polynomial unique. 相似文献
13.
In this paper we give first a new combinatorial interpretation of the coefficients of chromatic polynomials of graphs in terms of subsets of permutations. Motivated by this new interpretation, we introduce next a combinatorially defined polynomial associated to a directed graph, and prove that it is related to chromatic polynomials. These polynomials are a specialization of cover polynomials of digraphs.I am grateful to the Swiss National Science Foundation for its partial financial supportFinal version received: June 25, 2003 相似文献
14.
It is well known that (-∞,0) and (0,1) are two maximal zero-free intervals for all chromatic polynomials. Jackson [A zero-free interval for chromatic polynomials of graphs, Combin. Probab. Comput. 2 (1993), 325-336] discovered that is another maximal zero-free interval for all chromatic polynomials. In this note, we show that is actually a maximal zero-free interval for the chromatic polynomials of bipartite planar graphs. 相似文献
15.
许进 《数学物理学报(B辑英文版)》2004,24(4):577-582
A new recursive vertex-deleting formula for the computation of the chromatic polynomial of a graph is obtained in this paper. This algorithm is not only a good tool for further studying chromatic polynomials but also the fastest among all the algorithms for the computation of chromatic polynomials. 相似文献
16.
Jay R Goldman J.T Joichi Dennis E White 《Journal of Combinatorial Theory, Series B》1978,25(2):135-142
This paper studies the relationship between the rook vector of a general board and the chromatic structure of an associated set of graphs. We prove that every rook vector is a chromatic vector. We give algebraic relations between the factorial polynomials of two boards and their union and sum, and the chromatic polynomials of two graphs and their union and sum. 相似文献
17.
Eunice Mphako-Banda 《Quaestiones Mathematicae》2019,42(2):207-216
The 0-defect polynomial of a graph is just the chromatic polynomial. This polynomial has been widely studied in the literature. Yet little is known about the properties of k-defect polynomials of graphs in general, when 0 < k ≤ |E(G)|. In this survey we give some properties of k-defect polynomials, in particular we highlight the properties of chromatic polynomials which also apply to k-defect polynomials. We discuss further research which can be done on the k-defect polynomials. 相似文献
18.
Adam Bohn 《Graphs and Combinatorics》2014,30(2):287-301
We define a biclique to be the complement of a bipartite graph, consisting of two cliques joined by a number of edges. In this paper we study algebraic aspects of the chromatic polynomials of these graphs. We derive a formula for the chromatic polynomial of an arbitrary biclique, and use this to give certain conditions under which two of the graphs have chromatic polynomials with the same splitting field. Finally, we use a subfamily of bicliques to prove the cubic case of the α + n conjecture, by showing that for any cubic integer α, there is a natural number n such that α + n is a chromatic root. 相似文献
19.
关于图的色多项式的若干问题 总被引:4,自引:0,他引:4
<正> 设G是连通的无向的标定的(p,q)图.集S={1,2,…,t}.G的一个t-着色σ是G的点的集V(G)到S内的一个映射,满足条件:若u,v∈V(G)在G中邻接,则σu≠σv.G的不同的t-着色的总数f(G;t)是t的一个p次多项式.(关于色多项式的一般论述,下文未注明出处的结果及未给出定义的名词与记号均参见[1]).这个多项式记作 相似文献
20.
On Chromatic Polynomials of Some Kinds of Graphs 总被引:1,自引:0,他引:1
Rong-xiaHao Yan-peiLiu 《应用数学学报(英文版)》2004,20(2):239-246
In this paper,a new method is used to calculate the chromatic polynomials of graphs.The chro-matic polynomials of the complements of a wheel and a fan are determined.Furthermore,the adjoint polynomialsof F_n with n vertices are obtained.This supports a conjecture put forward by R.Y.Liu et al. 相似文献