围长至少是12的平面图的均匀聚集划分

图$G$的一个均匀$({mathcal{O}}^{1}_{k}, {mathcal{O}}^{2}_{k}, ldots, {mathcal{O}}^{m}_{k})$-划分是指把图$G$的点集$V(G)$划分成$m$个非空子集$V_{1}$, $V_{2}$, ldots, $V_{m}$使得对于任意的${1, 2, ldots, m}$, $G[V_{i}]$都是连通分支的阶数至多是$k$的图, 并且对于任意一对不同的$i, jin{1,ldots, m}$都有$-1leq|V_{i}|-|V_{j}|leq1$, 该划分又叫做均匀$k$聚集$m$-划分. 在本文中, 我们证明了每一个最小度$delta(G)geq2$, 围长$g(G)geq12$的平面图对于任意的整数$mgeq2$都存在一个均匀$({mathcal{O}}^{1}_{7}, {mathcal{O}}^{2}_{7}, ldots, {mathcal{O}}^{m}_{7})$-划分.     

围长至少为6的平面图的线性染色

如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数.论文证明了对于每一个最大度为△(G)围长至少为6的平面图G有lc(G)≤「(Δ(G))/2]+3,并且当△(G)■{4,5,…,12}时, lc(G)≤「(Δ(G))/2」+2.     

围长至少为6的平面图的邻点可区别边染色

邻点可区别边染色是指图G有一个正常边染色且任意两个相邻顶点的颜色集合不相等.邻点可区别边色数是指使图G有一个邻点可区别边染色的最小颜色数值,记作χ_α’(G).本文证明了:若图G是围长至少为6的正常平面图,则有χ_α’(G)≤max{6,△(G)+1}.     

围长至少为5的平面图的线性染色

如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数本文证明了对于每一个最大度为△(G)且围长至少为5的平面图G有lc(G)≤[△(G)/2]+5,并且当△(G)∈{7,8,…,14...     

围长至少为5的IC-可平面图的邻点可区别边染色

给图G一个正常k-边染色φ,对G的任意两个相邻的顶点u和v,若满足与u关联的边所染颜色集合和与v关联的边所染颜色的集合不同,则称φ为图G的k-邻点可区别边染色.用χ’_a(G)表示图G的邻点可区别边色数,即使得G有一个k-邻点可区别边染色的最小正整数k.通过运用权转移方法研究围长至少为5的正常IC-可平面图的邻点可区别边染色,得到了χ’_a(G)≤max{Δ(G)+2,11}.     

围长至少为4的平面图的邻点可区别边色数

图G的邻点可区别边染色是G的正常边染色,使得每一对相邻顶点有不同的颜色集合．G的邻点可区别边色数X＇a（G）是使得G有一个k-邻点可区别边染色的最小正整数七．本文证明了：若G是围长至少为4且最大度至少为6的平面图,则X＇a（G）≤△＋2．     

围长不小于6且最大度至少为8的平面图的无圈列表边染色

对图G的一个正常边染色,如果图G的任何一个圈至少染三种颜色,则称这个染色为无圈边染色.若L为图G的一个边列表,对图G的一个无圈边染色φ,如果对任意e∈E(G)都有ф(e)∈L(e),则称ф为无圈L-边染色.用a′_(list)(G)表示图G的无圈列表边色数.证明若图G是一个平面图,且它的最大度△≥8,围长g(G)≥6,则a′_(list)(G)=△.     

围长至少是7的1-平面图是$(1,1,1,0)$-可染的

一个图称为是1-平面图的, 如果它可以画在一个平面上使得它的每条边最多交叉另外一条边.本文证明了围长大于等于7的1-平面图是$(1,1,1,0)$-可染的.     

平面图的绑定数

图G的绑定数b(G)是指边集合的最少边数,当这个边集合从G中去掉后所 得图的控制数大于G的控制数． Fischermann等人在[3]中给出了两个猜想: (1)如果 G是一个连通的平面图且围长g(G)≥4,则b(G)≤5;(2)如果G是一个连通的平面图且 围长g(G)≥5,则b(G)≤4．设n3表示度为3的顶点个数,r4和r5分别表示长为4和 5的圈的个数．本文,我们证明了如果r4<(5n3)/2 10,则猜想1成立;如果r5<12,则猜 想2成立．     

6-圈至多含一弦平面图的线性荫度

线性森林是指每个连通分支都是路的图.图G的线性荫度la(G)等于将其边分解为k个边不交的线性森林的最小整数k.文中利用权转移方法证明了,若G是一个最大度大于等于7且每个6-圈至多含一条弦的平面图,则la(G)=「(△(G))/2」.     

New upper bounds on linear coloring of planar graphs

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph G is the smallest number of colors in a linear coloring of G. In this paper, it is proved that every planar graph G with girth g and maximum degree Δ has(1)lc(G) ≤Δ 21 if Δ≥ 9; (2)lc(G) ≤「Δ/2」 + 7 ifg ≥ 5; (3) lc(G) ≤「Δ/2」 + 2 ifg ≥ 7 and Δ≥ 7.     

直径为3的3-正则简单平面图的完全刻画

通过对子图和围长的研究,完全刻画了直径为3的3-正则简单平面图,获得了这类图仅有的11个非同构图.     

Acyclic edge colorings of planar graphs and seriesparallel graphs

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1. This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation of Shandong Province (Grant No. Y2008A20).     

Light subgraphs in planar graphs of minimum degree 4 and edge‐degree 9

A graph H is light in a given class of graphs if there is a constant w such that every graph of the class which has a subgraph isomorphic to H also has a subgraph isomorphic to H whose sum of degrees in G is ≤ w. Let be the class of simple planar graphs of minimum degree ≥ 4 in which no two vertices of degree 4 are adjacent. We denote the minimum such w by w(H). It is proved that the cycle C_s is light if and only if 3 ≤ s ≤ 6, where w(C₃) = 21 and w(C₄) ≤ 35. The 4‐cycle with one diagonal is not light in , but it is light in the subclass consisting of all triangulations. The star K_1,s is light if and only if s ≤ 4. In particular, w(K_1,3) = 23. The paths P_s are light for 1 ≤ s ≤ 6, and heavy for s ≥ 8. Moreover, w(P₃) = 17 and w(P₄) = 23. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 261–295, 2003     

The color space of a graph

If k is a prime power, and G is a graph with n vertices, then a k‐coloring of G may be considered as a vector in $\mathbb{GF}$(k)ⁿ. We prove that the subspace of $\mathbb{GF}$(3)ⁿ spanned by all 3‐colorings of a planar triangle‐free graph with n vertices has dimension n. In particular, any such graph has at least n − 1 nonequivalent 3‐colorings, and the addition of any edge or any vertex of degree 3 results in a 3‐colorable graph. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 234–245, 2000     

广义Petersen图的弱点传递性

图X称为弱点传递图如果X的自同态幺半群EndX在顶点集V(X)上的作用是传递的 .本文给出了广义Petersen图是二分图的充要条件 ,刻划了奇围长小于 9的广义Petersen图的弱点传递性 ,作为推论给出了所有h ≤ 1 5的弱点传递的广义Pe tersen图P(h ,t) .