P(G,λ)=nk[k n-k](λ)k+l图的刻画

应用色多项式的性质.讨论了具有色多项式图的结构,刻画了具有这种色多项式的全部色等价图.     

广义Pòlya组合计数方法

文中引入了P-置换图的概念．作为置换群的指标多项式和函数等价类配置多项式的推广形式分别定义了P-置换图的容量指标多项式与色权多项式,并给出了递归公式和相关定理,由此建立了计算P-置换图的色权多项式的一般方法和P-置换图的色轨道多项式的表达公式．Polya计数定理是这一公式当约束图是空图时的特例．最后给出了P-置换图的色权多项式的一些基本性质和两个计算实例．     

广义P$\grave{\bf o}$lya 组合计

文中引入了P-置换图的概念．作为置换群的指标多项式和函数等价类配置多项式的推广形式分别定义了P-置换图的容量指标多项式与色权多项式，并给出了递归公式和相关定理，由此建立了计算P-置换图的色权多项式的一般方法和P-置换图的色轨道多项式的表达公式．Pblya计数定理是这一公式当约束图是空图时的特例．最后给出了P-置换图的色权多项式的一些基本性质和两个计算实例．     

具有色多项式的图

本文讨论了色多项式为的图的结构,给出了具有这种色多项式的全部色等价图.     

P(G,λ)=sum(n/k[k,n-k](λ)_(k+l)图的刻画

应用色多项式的性质 .讨论了具有色多项式 ∑k≤ nnk　 kn - k (λ) k+l 图的结构 ,刻画了具有这种色多项式的全部色等价图 .     

正则树的双变量色多项式研究

最近Klaus Dohmen等人提出新的双变量色多项式概念,对此,本文提出—个—般性的减边公式.通过反复运用该公式,可以方便求得任何简单图的双变量色多项式.由此减边公式,研究了一些特殊图和多分支图的双变量色多项式公式.本文还研究了由互不相连的多个子图都与某个顶点相连而成的图的双变量色多项式计算的删点公式以及简单图的双变量色多项式系数和问题.进而,本文提出—个新概念—正则树.利用这个减边公式,研究了正则树的双变量色多项式计算公式和—些性质,以及正则树整子图的双变量色多项式公式及其有关性质.     

具有色多项式∏∑(ui)/(k)(k)/(ui-k)(λ)k的图

本文利用色多项式的性质,讨论了具有色多项式∏i∑kui/k（k/ui-k）（λ）k的图的结构,给出了具有这种色多项式的全部色等价图.     

P（G，λ）＝∑t／k[^kn—k]（λ）k＋l图的刻画

应用多项式的性质,讨论了具有色多项式∑k≤nt/k[^k n-k](λ)k l图的结构。刻画了具有这种色多项式的全部色等价图。     

去掉一些连续弦的轮图的补图的色多项式

本文给出计算图的色多项式的新方法。特别的,对轮图中去掉一些连续弦后所得到的图的补图,给出了它的色多项式的计算公式。     

关于两类特殊图的色多项式唯一性

本文用全新的方法证明了两类图的色多项式唯一性,推广了Beatrice Loe-rine关于广义θ-图的色多项式唯一性的结论。     

On chromatic and flow polynomial unique graphs

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.     

The chromatic polynomial of fatgraphs and its categorification

Motivated by Khovanov homology and relations between the Jones polynomial and graph polynomials, we construct a homology theory for embedded graphs from which the chromatic polynomial can be recovered as the Euler characteristic. For plane graphs, we show that our chromatic homology can be recovered from the Khovanov homology of an associated link. We apply this connection with Khovanov homology to show that the torsion-free part of our chromatic homology is independent of the choice of planar embedding of a graph. We extend our construction and categorify the Bollobás-Riordan polynomial (a generalization of the Tutte polynomial to embedded graphs). We prove that both our chromatic homology and the Khovanov homology of an associated link can be recovered from this categorification.     

Approximations for chromatic polynomials

A sequence of finite graphs may be constructed from a given graph by a process of repeated amalgamation. Associated with such a sequence is a transfer matrix whose minimum polynomial gives a recursion for the chromatic polynomials of the graphs in the sequence. Taking the limit, a generalised “chromatic polynomial” for infinite graphs is obtained.     

Computing clique and chromatic number of circular-perfect graphs in polynomial time

A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel et al. in Combinatorica 1(2):169–197, 1981). Perfect graphs have the key property that clique and chromatic number coincide for all induced subgraphs; we address the question whether the algorithmic results for perfect graphs can be extended to graph classes where the chromatic number of all members is bounded by the clique number plus one. We consider a well-studied superclass of perfect graphs satisfying this property, the circular-perfect graphs, and show that for such graphs both clique and chromatic number are computable in polynomial time as well. In addition, we discuss the polynomial time computability of further graph parameters for certain subclasses of circular-perfect graphs. All the results strongly rely upon Lovász’s Theta function.     

The odd–even invariant for graphs

The odd–even invariant for graphs is the graphic version of the odd–even invariant for oriented matroids. Here, simple properties of this invariant are verified, and for certain graphs, including chordal graphs and complete bipartite graphs, its value is determined. The odd–even chromatic polynomial is introduced, its coefficients are briefly studied, and it is shown that the absolute value of this polynomial at −1 equals the odd–even invariant, in analogy with the usual chromatic polynomial and the number of acyclic orientations.     

Signed graph coloring

Coloring a signed graph by signed colors, one has a chromatic polynomial with the same enumerative and algebraic properties as for ordinary graphs. New phenomena are the interpretability only of odd arguments and the existence of a second chromatic polynomial counting zero-free colorings. The generalization to voltage graphs is outlined.     

Edge coloring nearly bipartite graphs

We give a simple polynomial time algorithm to compute the chromatic index of graphs which can be made bipartite by deleting a vertex. An analysis of this algorithm shows that for such graphs, the chromatic index is the roundup of the fractional chromatic index.     

关于Q-树偶次整子图色性的一族反例(英文)

Chao ,Li和Xu[1 ],韩伯棠 [2 ,3]和ThomasWanner[4 ]证明 ,以q 树 ,qk 树和q 树整子图的色多项式为色多项式的图是唯一的 ,即它们本身 .但本文 ,我们证明了q 树的偶次整子图的色多项式 ,除本身外 ,至少对应一类新图 ,而且指出这类图 ,即使色多项式仅有整根也不能三角化 .     

Enumerative Properties of Ferrers Graphs

We define a class of bipartite graphs that correspond naturally with Ferrers diagrams. We give expressions for the number of spanning trees, the number of Hamiltonian paths when applicable, the chromatic polynomial and the chromatic symmetric function. We show that the linear coefficient of the chromatic polynomial is given by the excedance set statistic.