具有色多项式的图

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

双圈图按谱半径的排序

一个n阶简单连通图G被称为双圈图,如果它的边数是n+1.记B(n)是n阶双圈图的全体.本文确定了B(n)(n≥20)中谱半径的第六大至第十大值和对应的图.     

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

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

树,单圈图,双圈图依谱矩的排序

设G=(V(G),E(G))是一个n阶简单图,V(G),E(G)分别为图G的顶点集和边集.G的k阶谱矩sk(G)为G的所有特征值λ1,λ2,···,λn的k次幂之和,即sk(G)=n i=1λi k.该文首先列出图的五种变换,然后得到了其对任意图的零到四阶谱矩的变化规律,最后依次给出了树和单圈图依谱矩序列S4的字典序分别排在前4-6位和后4-6的图及其特征以及双圈图依谱矩序列S4的字典序排在前6位和后6位的图及其特征.     

SG类图簇的伴随多项式的因式分解及色性分析

设G是任意的P阶连通图，V(G)={V1，V2，…，Vp}，Sn 1是具有度序列(n，1，1，…，1)的．n 1阶星图．令(ψ)^G(i）(n，P)表示图G的第i个顶点与Sn 1的n度点重迭后得到的图；Srp 1^G（i）表示rG的每个分支的第i个顶点依次与Sr 1的r个1度点重迭后得到的图，这里n≥1，P≥2，1≤i≤P．我们通过研究图的伴随多项式的因式分解，证明了两个图簇Srp 1^G(i）U（r-1)K1与(r-1)GUψG(i)(r,P)的补图是色等价的，但它们均不是色唯一的，从而推广了张秉儒证明的文[14]中的定理1。     

色多项式对图的刻画

By means of the chromatic polynomials, this paper provided a necessary and sufficient condition for the graph G being a mono-cycle graph(the Theorem 1), a first class bi-cycle graph and a second class bicycle graph(the Theorem 2), respectively.     

图的色多项式系数之和问题的研究

本文给出了任何简单图G(V,E)的色多项式P(G，λ)=∑i=1^vαiλ^i系数之和的公式：∑i=1^vαi={0ε≠0 1ε=0;并进行了证明，从而为判别一个多项式不是图的色多项式提供了一个必要条件．同时也分别给出了树、2-树、圈、轮图和完全图的色多项式系数绝对值之和的表达式．最后证明了任何简单连通图的色多项式系数绝对值之和∑i=1^v|αi|与边ε成正比，且必满足2^v-1≤∑i=1^v|αi|≤пi=1^vi．     

同一个色多项式图的结构特征问题

研究了图的色多项式,给出了用图的结构特征描述的色多项式表达式.     

色多项式的Akiyama-Harary问题

J.Akiyama和F.Harary提出:是否存在非自补图G,使得G与其补图G>有相同的色多项式,本文给出一个肯定的回答,并证明了:这样的平面图G仅存在有限多个。     

若干图簇的伴随多项式的因式分解及色性分析

我们通过研究图的伴随多项式的因式分解,给出了证明非色唯一图的一种新方法,同时得到若干图簇的色等价图的结构定理.     

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

两类只含整数根的色多项式

研究了两类只含整数根的色多项式,给出其相应图G为弦图的必要条件,并完全刻画了G的色等价类[G].     

The interlace polynomial of a graph

Motivated by circle graphs, and the enumeration of Euler circuits, we define a one-variable “interlace polynomial” for any graph. The polynomial satisfies a beautiful and unexpected reduction relation, quite different from the cut and fuse reduction characterizing the Tutte polynomial.It emerges that the interlace graph polynomial may be viewed as a special case of the Martin polynomial of an isotropic system, which underlies its connections with the circuit partition polynomial and the Kauffman brackets of a link diagram. The graph polynomial, in addition to being perhaps more broadly accessible than the Martin polynomial for isotropic systems, also has a two-variable generalization that is unknown for the Martin polynomial. We consider extremal properties of the interlace polynomial, its values for various special graphs, and evaluations which relate to basic graph properties such as the component and independence numbers.     

The chromatic polynomial of an unlabeled graph

We investigate the chromatic polynomial χ(G, λ) of an unlabeled graph G. It is shown that $\text{χ(G, λ) = (}\text{1}\text{|A(g)|}\text{) Σ}{}_{\mathrm{\pi \; \in \; A(g)}}\text{χ(g, π, λ)}$, where g is any labeled version of G, A(g) is the automorphism group of g and χ(g, π, λ) is the chromatic polynomial for colorings of g fixed by π. The above expression shows that χ(G, λ) is a rational polynomial of degree n = |V(G)| with leading coefficient $\text{1}\text{|A(g)|}$. Though χ(G, λ) does not satisfy chromatic reduction, each polynomial χ(g, π, λ) does, thus yielding a simple method for computing χ(G, λ). We also show that the number N(G) of acyclic orientations of G is related to the argument λ = ?1 by the formula $\text{N(G) = (}\text{1}\text{|A(g)|}\text{) Σ}{}_{\mathrm{\pi \; \in \; A(g)}}\text{(?1)}{}^{\mathrm{s(\pi )}}\text{χ(g, π, ?1)}$, where s(π) is the number of cycles of π. This information is used to derive Robinson's (“Combinatorial Mathematics V” (Proc. 5th Austral. Conf. 1976), Lecture Notes in Math. Vol. 622, pp. 28–43, Springer-Verlag, New York/Berlin, 1977) cycle index sum equations for counting unlabeled acyclic digraphs.     

图K_n-E(k_0P_3(∪ri=1k_iP(q_i-1)))的色唯一性

记δｎ＝ｋ≤ｎｋｎ－ｋ，在本文中证明了：ｒ∈Ｎ，若ｉ∈｛１，２，…，ｒ｝，ｑｉ（＞５）都是素数，并且［（δｑｉ－１－１）！＋１］／δｑｉ－１是正整数，则图簇Ｋｎ－Ｅｋ０Ｐ３∪ｋ１Ｐｑ１－１∪ｋ２Ｐｑ２－１∪…∪ｋｒＰｑｒ－１是色唯一的，推广了文［１］的结果     

一类树并的补图的色唯一性

彻底解决了一类不可约树并的补图是色唯一的 ,并得到了一些图的伴随多项式的最小根的重要规律 .     

THE TOTAL CHROMATIC NUMBER OF PSEUDO-OUTERPLANAR GRAPHS

A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g.     

On the complete chromatic number of Halin graphs

ThisresearchissupportedbytheNationalNaturalScienceFoundationofChina.Write.1.IntroductionDefinition1.FOrany3-connectedplanargraphG(V,E,F)withA(G)23,iftheboundaryedgesoffacefowhichisadjacenttotheothersareremoved,itbecomesatree,andthedegreeofeachvertexofV(fo)is3,andthenGiscalledaHalingraph;foiscalledtheouterfaceofG,andtheotherscalledtheinteriorfaces,thevenicesonthefacefoarecalledtheoutervenices,theoillersarecalledtheinterior...ti..,tll.ForanyplanargraphG(V,E,F),f,f'eF,fisadjacenttof'ifan…