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

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

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

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

高度平面图完备色数的一个刻划

设G是一个平面图,△(G)为G的最大度．G的完备色数x     

不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界

图G的一个边分解是指将G分解成子图G_1,G_2,…,G_m使得E(G)=E(G_1)=∪E(G_2)∪…∪E(G_m),且对于i≠j,E(G_i)∩E(G_j)=?.一个线性k-森林是指每个分支都是长度最多为k的路的图.图G的线性k-荫度la_k(G)是使得G可以边分解为m个线性k-森林的最小整数m.显然,la_1(G)是G的边色数χ'(G); la_∞(G)表示每条分支路是无限长度时的情况,即通常所说的G的线性荫度la(G).利用权转移的方法研究平面图的线性2-荫度la_2(G).设G是不含有5-圈和相邻4-圈的平面图,证明了若G连通且δ(G)≥2,则G包含一条边xy使得d(x)+d(y)≤8或包含一个2-交错圈.根据这一结果得到其线性2-荫度的上界为[△/2]+4.     

平面图的单射边染色

图G的k-单射边染色是指映射f:E(G)→{1,2,…,k},若e₁,e₂和e₃是G中的连续边,则f (e₁)≠f(e₃).称χ’_i(G)=min{k|G存在k-单射边染色}为图的单射边染色数.本文证明了:对g(G)≥6的平面图G,有χ’_i(G)≤3Δ(G)-2,对g(G)≥26且Δ(G)≤3的平面图G,有χ’_i(G)≤4,对g(G)≥16且Δ(G)≥4的平面图G,有χ’_i(G)≤Δ(G)+1,其中g(G)表示平面图G的围长.     

2-外平面图的无圈边色数

一个图G的无圈边染色是一个止常的边染色使得其不产生双色圈．Alon,Sudakov和Zaks（2001）猜想：每一个简单图G是无到（△（G）＋2）-边可染的,其中△（G）是G的最大度．本文对2-外平面图族证明了该猜想成立．     

IC-平面图的线性荫度

图G的边分解是指将G分解成子图G₁,G₂,...,G_m,使得E(G)-E(G₁)∪…∪.E(G_m),且对任意i≠j,有E(G_i)∩E(G_j)=?.若一个森林的每个连通分支都是路,则称该森林为线性森林.图G的线性荫度la(G)是指使得G可以边分解为m个线性森林的最小整数m.本文证明了Δ(G)≥15的IC-平面图G的线性荫度为[Δ(G)/2],这里Δ(G)是图G的最大度.     

若干平面图的完备色数

设G是无割点平面图,X_c(G)为G的点边面完备色数,p=|V(G)|.本文证明了如G为Δ(G)≥7的外平面图,或G为p≥9且Δ(G)≥p-2,或G为Δ(G)≥14的极大平面图,则 X_c(G)=Δ(G)+1.     

平面图3色可染的一个充分条件

Steinberg猜想既没有4-圈又没有5-圈的平面图是3色可染的. Xu, Borodin等人各自独立地证明了既没有相邻三角形又没有5-和7-圈的平面图是3 色可染的. 作为这一结果的推论, 没有4-, 5-和7-圈的平面图是3色可染的. 本文证明一个比此推论更接近Steinberg猜想的结果, 设G是一个既没有4-圈又没有5-圈的平面图, 若对每一个k∈{3, 6, 7}, G都不含(k, 7)-弦, 则G是3色可染的, 这里的(k, 7)-弦是指长度为7+k-2的圈的一条弦, 它的两个端点将圈分成两条路, 一条路的长度为6, 另一条路的长度为k-1.     

1-平面图的线性荫度

图G的边分解是指将G分解成子图G₁,G₂,…,G_m,使得E(G)=E(G₁)∪…∪E(G_m),且对任意i≠j有E(G_i)∩E(G_j)=?.若一个森林的每个连通分支都是路,则称该森林为线性森林.图G的线性荫度la(G)是指使得G可以边分解为m个线性森林的最小整数m.本文利用权转移方法证明了Δ(G)≥25的1-平面图G的线性荫度为[Δ(G)/2],这里Δ(G)是图G的最大度.     

Upper bounds on the linear chromatic number of a graph

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is a union of vertex-disjoint paths. The linear chromatic number of G is the smallest number of colors in a linear coloring of G.Let G be a graph with maximum degree Δ(G). In this paper we prove the following results: (1) ; (2) if Δ(G)≤4; (3) if Δ(G)≤5; (4) if G is planar and Δ(G)≥52.     

Linear coloring of planar graphs with large girth

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 of the graph G is the smallest number of colors in a linear coloring of G. In this paper we prove that every planar graph G with girth g and maximum degree Δ has if G satisfies one of the following four conditions: (1) g≥13 and Δ≥3; (2) g≥11 and Δ≥5; (3) g≥9 and Δ≥7; (4) g≥7 and Δ≥13. Moreover, we give better upper bounds of linear chromatic number for planar graphs with girth 5 or 6.     

Linear choosability of sparse graphs

A linear coloring is a proper coloring such that each pair of color classes induces a union of disjoint paths. We study the linear list chromatic number, denoted , of sparse graphs. The maximum average degree of a graph G, denoted mad(G), is the maximum of the average degrees of all subgraphs of G. It is clear that any graph G with maximum degree Δ(G) satisfies . In this paper, we prove the following results: (1) if and Δ(G)≥3, then , and we give an infinite family of examples to show that this result is best possible; (2) if and Δ(G)≥9, then , and we give an infinite family of examples to show that the bound on cannot be increased in general; (3) if G is planar and has girth at least 5, then .     

由轮图导出的某些平面图类的星色数

图的星色数是通常色数概念的推广.本文求出了几类由轮图导出的平面图的星色数.前两类是由3-或5-轮图经细分等构造出的,其星色数分别为2+2/(2n+1),2+3/(3n+1)和2+3/(3n-1).第三类平面图是由n-轮图经过Hajos构造得到的,其星色数为3+1/n.本类图的星色数结果推广了已有结论.     

Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiamik (Math. Slovaca 28 (1978), 139–145) and later Alon et al. (J Graph Theory 37 (2001), 157–167) conjectured that for any simple graph G with maximum degree Δ. In this article, we confirm this conjecture for planar graphs of girth at least 4.     

Total Colorings of Planar Graphs without Small Cycles

Let G be a planar graph with maximum degree Δ. It is proved that if Δ ≥ 8 and G is free of k-cycles for some k ∈ {5,6}, then the total chromatic number χ′′(G) of G is Δ + 1. This work is supported by a research grant NSFC(60673047) and SRFDP(20040422004) of China. Received: February 27, 2007. Final version received: December 12, 2007.     

图的D(2)点可区别星边色数的一个上界

提出了图的D(β)点可区别星边染色及D(β)点可区别星边色数的概念,并用Lovasz局部引理证明了在β=2时,若G=(V,E)是一个最小度为δ(G)>3的简单无向图,则X_(2-vds)(G)≤24△2/3]。     

Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable

The Total Coloring Conjecture, in short, TCC, says that every simple graph is (Δ+2)-totally-colorable where Δ is the maximum degree of the graph. Even for planar graphs this conjecture has not been completely settled yet. However, every planar graph with Δ≥9 has been proved to be (Δ+1)-totally-colorable. In this paper, we prove that planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable.     

没有5-圈的平面图的BB-染色

设H为G的一个生成子图,（G,H）的一个BB-k-染色是指一个映射f：V（G）→{1,2,…,k},当uv∈E（H）,｜f（u）-f（v）｜≥2;当uv∈E（G）／E（H）,｜f（u）-f（v）｜≥1.定义（G,H）的BB色数x_b（G,H）为最小的整数k,使得（G,H）是BB-k可染的.本文研究了对于任意的连通,非二部平面图G,且G没有5-圈,都存在一棵生成树T,使得x_b（G,T）=4.