关于K4(2,3,3,δ,ε,η)色性问题的一个研究

证明：在K4-同胚图K4(2，3，3，δ，ε，η)图簇中，任何两个不同构的图都不是色等价的，这一结论从色多项式的角度刻划了K4同胚图K4(2，3，3，δ，ε，η)的结构特征，为进一步研究K4-同胚图的色唯一性奠定了基础。     

完全t部图 K(n1,n2,…,nt)的色唯一性

本文使用比较两个色等价图的色划分数的方法,得出了完全t部图的色等价图类仍为完全t部图的一般形式数值条件,进一步得出了K(n1,n2,n3)和K(n1,n2,n3,n4)为色唯一图的一般形式数值条件.     

关于完全三部图K(n,n,n+4)的色唯一性

通过比较两个图的色多项式的系数(本文使用了五独立集数)、顶点集、边集、三角形和四圈的个数,证明了K(2,2,6)是色唯一图,从而部分地回答了文[5],[7]中遗留的一个问题,并得到图K(n,n,n 4)(n=2或n 4)是色唯一的.     

关于完全t部图K(n1,n2,…,nt)的色唯一性

设P（G，λ）是图G的色多项式，如果对任意使P（G，λ）=P（H，λ）的图H都与G同构，则称G是色唯一图。这里通过比较图的特征子图的个数，讨论了由Koh和Teo在文献[1]中提出的问题（若｜ni-nj｜≤2，1≤i，j≤t且min{n1，n2，…，nt}充分大，K（n1，n2，…，nt）是否为色唯一图？）。证明了，若｜ni—nj｜≤2且t↑∑↑i=1 ni〉t^2/2＋t√t-1，则K（n1，n2，…，nt）是色唯一图；若αi=0或k，t↑∑↑i=1 n＋αi〉t^2k^2/8＋｜tk｜/2√t-1，则K（n＋α1，n＋α2，…，n＋αt）是色唯一图。其条件比文献[4]中的条件较好一些。     

关于完全三部图K(m,n,r)的色唯一性

本文研究完全三部图K(m,n,r)的色唯一性问题，通过比较两个色等价图的色划分数的方法，得出两个关于K(m,n,r)为色唯一图的一般形式数值条件，基本上解决了K(m,n,r)为色唯一图的判定问题．     

关于K4-同胚图色性的研究

We introduce a new method for studying the chromaticity of K4-homeomorphs, by which some new results are obtained.     

完全t部图K(n1,n2…nt)的色唯一性

本文使用比较两个色等价图的色划分数的方法,得出了完全t部图的色等价图类仍为完全t部图的一般形式数值条件,进一步得出了K(n₁,n₂,n₃)和K(n₁,n₂,n₃,n₄)为色唯一图的一般形式数值条件。     

一类K-4与路点粘接补图的色唯一性

利用图的伴随多项式的最小极及第四项系数，给出了一类K4^-与路点粘接补图色唯一的充要条件。     

完全三部图K(n-k,n,n)的色唯一性

通过对图的特征子图个数的比较,给出了图K(n-k,n,n)色唯一性的数值条件.     

图K(m,n)+S的色性

设S是完全图Km 1的任一有s条边的子图,即|E(S)|=s,E(S)(∪)E(Km 1),V(S)(∪)V(Km 1).图Km 1-E(S)简单地表示为Km 1-S,而Km 1-S关于Km 1的补图记为(Km 1-S).空图Nm与(Km 1-S)的联图记为Nm∨(Km 1-S).K sm 1(m,m 1)表示图集{Nm∨(Km 1-S)| S是Km 1的子图,|S|=s}.本文证明了当m≥s 2且s≥1,〈S〉是E(s)在完全图Km 1的边导出子图并且〈S〉是二部图时,联图Nm∨(Km 1-S)为色唯一图的充要条件是〈S〉是没有割点的连通图(即〈S〉是2-连通的或〈S〉≌Ki,i=1,2)且是色唯一图.     

Sharp bounds for the number of 3‐independent partitions and the chromaticity of bipartite graphs

Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ??^?s(p,q) (resp., ??₂^?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph K_p,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ^?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? ₂^?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ^?s(p,q) (resp., G ∈ ?? ₂^?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ??^?s_i(p+i,q?i) where max and s_i = s ? i(p?q+i) (resp., a subset of ??₂^?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from K_p,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001     

Weak acyclic coloring and asymmetric coloring games

We introduce the notion of weak acyclic coloring of a graph. This is a relaxation of the usual notion of acyclic coloring which is often sufficient for applications. We then use this concept to analyze the (a,b)-coloring game. This game is played on a finite graph G, using a set of colors X, by two players Alice and Bob with Alice playing first. On each turn Alice (Bob) chooses a (b) uncolored vertices and properly colors them with colors from X. Alice wins if the players eventually create a proper coloring of G; otherwise Bob wins when one of the players has no legal move. The (a,b)-game chromatic number of G, denoted (a,b)-χ_g(G), is the least integer t such that Alice has a winning strategy when the game is played on G using t colors. We show that if the weak acyclic chromatic number of G is at most k then (2,1)-.     

The 3‐connectivity of a graph and the multiplicity of zero “2” of its chromatic polynomial

Let G be a graph of order n, maximum degree Δ, and minimum degree δ. Let P(G, λ) be the chromatic polynomial of G. It is known that the multiplicity of zero “0” of P(G, λ) is one if G is connected, and the multiplicity of zero “1” of P(G, λ) is one if G is 2‐connected. Is the multiplicity of zero “2” of P(G, λ) at most one if G is 3‐connected? In this article, we first construct an infinite family of 3‐connected graphs G such that the multiplicity of zero “2” of P(G, λ) is more than one, and then characterize 3‐connected graphs G with Δ + δ?n such that the multiplicity of zero “2” of P(G, λ) is at most one. In particular, we show that for a 3‐connected graph G, if Δ + δ?n and (Δ, δ₃)≠(n?3, 3), where δ₃ is the third minimum degree of G, then the multiplicity of zero “2” of P(G, λ) is at most one. © 2011 Wiley Periodicals, Inc. J Graph Theory     

一类平面图的色多项式及其根的计算方法

图的色多项式P（G,x）是对图G用z（正整数）种颜色正常着色的数目。现在我们在实数或复数域上考虑图的色多项式P（G,x）,并且Beraha＆Kahane发现了具有复色根无限接近于4的平面图族。由此本文得到了一类平面图的色多项式和它的根．     

Chromaticity of complete 6-partite graphs with certain star or matching deleted II

Let P(G,λ) be the chromatic polynomial of a graph G. Two graphs G and H are said to be chromatically equivalent, denoted G～H, if P(G,λ)=P (H,λ). We write [G]={H|H～G}. If[G]={G}, then G is said to be chromatically unique. In this paper, we first characterize certain complete 6-partite graphs with 6n+1 vertices according to the number of 7-independent partitions of G. Using these results, we investigate the chromaticity of G with certain star or matching deleted. As a by-product, many new families of chromatically unique complete 6-partite graphs with certain star or matching deleted are obtained.     

A Combined Logarithmic Bound on the Chromatic Index of Multigraphs

For a multigraph G, the integer round‐up of the fractional chromatic index provides a good general lower bound for the chromatic index . For an upper bound, Kahn 1996 showed that for any real there exists a positive integer N so that whenever . We show that for any multigraph G with order n and at least one edge, ). This gives the following natural generalization of Kahn's result: for any positive reals , there exists a positive integer N so that + c whenever . We also compare the upper bound found here to other leading upper bounds.     

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

本文给出了任何简单图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．     

CIRCULAR CHROMATIC NUMBER AND MYCIELSKI GRAPHS

For a general graph G, M(G) denotes its Mycielski graph. This article gives a number of new sufficient conditions for G to have the circular chromatic number Xc(M(G)) equals to the chromatic number X(M(G)), which have improved some best sufficient conditions published up to date.     

关于Mycielski图循环色数的猜想

通过引进Mycielski图点集的一类特殊划分,利用该划分在Mycielski图循环着色中的特点改进了如下猜想:完全图的Mycielski图的循环色数等于它的点色数.