不含4-,6-圈和相交三角形的平面图的无圈边色数

图G的一个边染色φ:E(G)→{1,2,…,k},若满足任意相邻边都染不同的颜色,且图G不存在双色圈,则称φ为图G的一个无圈k-边染色.图G的无圈边色数χ’_α(G)为使得图G有一个无圈k-边染色的最小正整数k.本文主要证明了对于无4-,6-圈且3-圈与3-圈不相交的平面图G,若Δ(G)≥9,则χ’_α(G)≤Δ(G)+1.     

无8-,9-和10-圈的平面图的3-可选择性

寻找平面图是3-或者4-可选择的充分条件是图的染色理论中一个重要研究课题,本文研究了围长至少是4的特殊平面图的选择数,通过权转移的方法证明了每个围长至少是4且不合8-圈,9-圈和10-圈的平面图是3-可选择的．     

关于无5-,6-及7-圈的平面图的3-可选性(英文)

本文证明了不含5-,6-及7-圈且三角形的距离大于等于2的平面图是3-可选的.     

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

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

不含5-圈和相邻6-圈的平面图的全染色

图的正常k-全染色是用k种颜色给图的顶点和边同时进行染色,使得相邻或者相关联的元素(顶点或边)染不同的染色.使得图G存在正常k-全染色的最小正整数k,称为图G的全色数,用χ″(G)表示.证明了若图G是最大度△≥6且不含5-圈和相邻6-圈的平面图,则χ″(G)=△+1.     

不含5-圈的平面图的无圈边着色

图G的一个无圈边着色是一个正常的边着色且不含双色的圈.图G的无圈边色数是图G的无圈边着色中所用色数的最小者.本文用反证法得到了不含5-圈的平面图G的无圈边色数的一个上界.     

不含4-圈和9-圈的平面图是(2,0,0)-可染的

设d_1,d_2,...d_k为尼个非负整数.若图G的顶点集V可划分成k个子集合V_1,V_2…,V_k,使得对于任意的i∈{1,2,...,k},由V_i导出的子图G[V_i]的最大度至多为d_i,则称图G是(d_1,d_2,...,d_k)-可染的.1976年,Steinberg猜想:不含4-圈和5-圈的平面图是(0,0,0)-可染的.在Steinberg猜想的驱动下,人们证明了以下三个结论:(1)对每一个i∈{5,6,7,8,9},不含4-圈和i-圈的平面图是列表(1,1,1)-可染的;(2)对每一个i∈{5,6,7,8,9},不含4-圈和i-圈的平面图是(1,1,0)-可染的;(3)对每一个i∈{5,6,7,8},不含4-圈和i-圈的平面图是(2,0,0)-可染的.为使结论(3)更加完整,本文证明不含4-圈和9-圈的平面图是(2,0,0)-可染的.     

不含5-圈和6-圈的平面图的(2,1)-全标号

图G的(2,1)-全标号是对图G的顶点和边的一个标号分配,使得:(1)任意两个相邻顶点标号不同;(2)任意两条相邻边标号不同;(3)任意顶点与其相关联的边标号至少相差2.两个标号的最大差值称为跨度,图G的所有(2,1)-全标号的最小跨度称为(2,1)-全标号数,记为λ_2~T(G).本文证明了如果G是一个?=p+5的平面图,且G不包含5-圈和6-圈,那么λ_2~T(G)=2?-p,p=1,2,3.     

不含4,6,8-圈的平面图是3-可染的

证明了每个不含4,6,8-圈的平面图是3-可染的.     

ON 3-CHOOSABIL ITY OF PL ANE GRAPHSON3 -CHOOSABIL ITY OF PL ANE GRAPHS WITHOUT 6-,7-AND 9-CYCLES

§ 1　 IntroductionAll graphs considered in this paper are finite,simple plane graphs.G=(V,E,F)denotes a plane graph,with V,E and F being the set of vertices,edges and faces of G,respectively.Two vertices u and v are adjacent,denoted by uv∈E,if there is an edge in Ejoining them.A vertex u is incident with an edge e if u is an endvertex of e.Two faces aresaid to be adjacent if they share a common edge.We use b(f) to denote the boundary of aface f.A face is incident with all vertices and e…     

不包含{4,8,9}-圈的平面图是3-可染的

主要围绕Steinberg提出猜想:每个不包含4-圈和5-圈的平面图都是3-可染色的,对一些平面图类展开研究,提出要解决的问题:不包含{4,8,9}-圈的平面图是3-可染的.现从四个方面:不包含{4,8,9}-圈的平面图G的一些结构性质;不包含{4,8,9}-圈的平面图G中内部非分离6-圈的性质;不包含{4,8,9}-圈的平面图G不包含内部的6-面;f0不是一个6-面来证明结论,即不包含{4,8,9}-圈的平面图是3-可染的.     

三正则平面图的对偶图的哈密顿性的注记

本文给出了三正则平面图的对偶图为哈密顿图的一个充分条件。     

不含有5-圈和k4平面图的森林分解

本文研究了不含有5-圈和K₄的平面图的森林分解问题.利用权转移法,证明了任意不含有5-圈和K₄的平面图能分解成三个森林,且其中有一个森林的最大度不超过2,这一结果推广了文献[2,3]中的结论.     

CYCLE SPACES OF GRAPHS ON THE SPHERE AND THE PROJECTIVE PLANE

Cycle base theory of a graph has been well studied in abstract mathematical field such matroid theory as Whitney and Tutte did and found many applications in pratical uses such as electric circuit theory and structure analysis, etc. In this paper graph embedding theory is used to investigate cycle base structures of a 2-(edge)-connected graph on the sphere and the projective plane and it is shown that short cycles do generate the cycle spaces in the case of ““““small face-embeddings““““. As applications the authors find the exact formulae for the minimum lengthes of cycle bases of some types of graphs and present several known results. Infinite examples shows that the conditions in their main results are best possible and there are many 3-connected planar graphs whose minimum cycle bases can not be determined by the planar formulae but may be located by re-embedding them into the projective plane.     

A SEVEN-COLOR THEOREM ON EDGE-FACE COLORING OF PLANE GRAPHS

1 IntroductionLet G be a plane graph with the vertex set V(G), the edge set E(G), the faCe set F(G),and the maximum degree A(G). The edge-face chromatic number X.I (G) of G is the ndnimumnunther of colors assigned to E(G) U F(G) such that aliy two adjacent or incident elements havedifferent colors. By the definition, X.,(G) 2 A(G) is trivial. In 1975, MelnikovI4J raised thefollowing conjecture.,Coniecture 1.1 For every plane graph G, X.J (G) 5 A(G) 3.The conjecture has been ton…     

消去图、覆盖图和均匀图的若干结果

设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献   

关于两类平面图及相关图的L(d1,d2)-标号问题

图G的L(2,1)标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥(2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)标号数λ(G)是使得G有max{f(v)V∈V(G)}=k的L(2,1)标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.本文将L(2,1)-标号推广到L(d1,d2)-标号,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d1,d2)-标号的上界,作为推论,本文证明了对上述几类图,有上述猜想成立.     

ON 3-CHOOSABILITY OF PLANE GRAPHS WITHOUT 6-,7- AND 9-CYCLES

The choice number of a graph G,denoted by X1(G),is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper,it is showed that X1 (G)≤3 for each plane graph of girth not less than 4 which contains no 6-, 7- and 9-cycles.     

含偶长圈的7点7边图的图设计

设λKν是ν阶λ重完全图，G是一个无孤立点的有限简单图,λKν的一个G-分拆(或G-设计，记为G-GDλ(ν))是指一个序偶(X，β)，其中X是完全图Kν的顶点集，β是Kν中同构于G的子图(称为区组)的族，使得Kν中每条边恰好出现在β的λ个区组中，本文完全解决了含偶长圈的十个7点7边图的图设计存在性问题。