平面图平方的最小度

设G是一个没有4-圈的平面图,G的平方图G2定义在V(G)上,使得2个点u和v在G2中是相邻的当且仅当它们在G中的距离为1或2.证明了:δ(G2)≤Δ(G) 33,并且当δ(G)≥4时有δ(G2)≤16.其中,δ(H)和Δ(H)分别表示图H的最小度和最大度.     

平面图边可重构的几个结果

本文得出几个平面图边可重构的结论:1.若 G 是平面图,δ(G)=4,且 G 没有次为5的点,则 G 是边可重构的。2.若 G 是平面图,δ(G)≥3,且 S_3为 G 中次为3的集合,又设 G—S_3为3连通的,G 无次为4的点。则 G 是边可重构的。     

关于互补平面图的A■iyama-Harary问题的一个注记(英文)

纠正了[1,2]中的几个错误。设G是一个简单图,■表示G的补图。若G与■均为平面图,则称G对应于一个CPGP。当n=7时,CPGP的总数为300;当n=8时,CPGP的总数为1101。因此,所有互补平面图偶(CPGP)的总数为1491。     

满足xyz=--+的变换图Gxyz

图G的变换图G--+以V(G)∪E(G)为其顶点集,对任意的α,β∈V(G)∪E(G),α和β在图G--+中邻接的条件如下:(ⅰ)α,β∈V(G), 且α和β在G中不相邻,(ⅱ) α,β∈E(G), 且α和β在G中不相邻,(ⅲ) α∈V(G),β∈E(G), 且它们在G中相关. 本文主要证明除了12个图外,G--+都不是可平面图, 以及对于图G, G--+ ≌Pn--+当且仅当G≌Pn.     

最大度为4的平面图的平方染色

证明了若G为最大度Δ(G)≤4且不含4,5,6-圈的平面图,则χ(G2)≤Δ(G)+7.     

最大度是4的可平面图是第一类图的充分条件

运用Discharge方法证明:最大度是4,且满足下列条件之一的可平面图G是第一类的.(1)G中不含长度为4至9的圈;(2)G中不含4-圈和5-圈,且任意两个3-面不关联于同一个顶点;(3)G中不含长度在5和8之间的圈,且任意两个3-圈,任意两个4-圈不关联于同一个顶点;(4)围长不小于4,G中不含有弦的8-圈,且任意两个4-面不关联于同一个顶点.     

△(G)=9且不含4-圈的平面图的全色数

用△(G)表示图G的顶点最大度.对平面图,当△(G)≥11时,已证明Vizing和Behzad的图的全色数猜想(TCC)是正确的.运用Dischrge方法证明了最大度为9且不含4-圈的平面图的全色数等于10.     

Δ(G)=9且不含4-圈的平面图的全色数

用Δ(G)表示图G的顶点最大度.对平面图,当Δ(G)≥11时,已证明Vizing和Behzad的图的全色数猜想(TCC)是正确的.运用Discharge方法证明了最大度为9且不含4-圈的平面图的全色数等于10.     

一类平面图的强边着色

图G的强边着色是正常边着色且任何长为3的路的边不着双色.图G的强边色数是G的所有强边着色中使用色数的最小者,记为χ′s(G).证明了如果图G是平面图且满足g(G)≥14,则χ′s(G)≤|(5Δ2-2Δ+1)/4|,其中g(G)表示图G的围长.     

围长为4的无7-,8-圈和15-圈平面图的3-选色

图G的选色数(记为χ_l(G)), 定义为最小的自然数k, 满足当对任一顶点给定k种颜色的列表, 且染色时每个顶点的颜色只能从自身的颜色列表 中选择时, 存在图G顶点的一个正常着色. 应用Discharging方法对上述问题进行研究, 证明了每个围长至少为4且不含7-圈, 8-圈和15-圈的平面图是3-可选择的.     

没有某些圈的平面图的3可选择性

设G=(V,E)是一个图,对G的每一点v给一颜色集L(v).G称为L列表可染的,如果存在G的点染色f满足:f(u)≠f(v),(u,v)∈E(G),且f(u)∈L(u),u∈V(G).G称为k可选择的,对于任何列表L(v)(这里每一个L(v)恰有k个元素)G都是L列表可染的.本文研究了没有某些圈的平面图的可选择性,证明了没有4,5,7,10圈的平面图是3可选择的.     

次立方平面图的单射边染色

如果3条边e₁,e₂,e₃按照此顺序形成一条长为3的路或者圈,则称这3条边是连续的.k-单射边染色是对图G的边进行染色,使得如果3条边e₁,e₂,e₃是连续的,那么,e₁和e₃染不同的颜色.图G的单射边色数为所有单射边染色中所用颜色最少的颜色数.文中考虑在限制围长条件下,次立方平面图G的单射边色数.     

自补图的平面性讨论

分析探讨了所有自补图的平面性及外可平面性，得出了v≤8的自补因是可平面的；v≤5的自补图是外可平面的。     

最大度为6且不含相交4-圈的三类平面图的全染色

设G是一个不含相交4-圈的平面图且Δ(G)≥6,证明了如果G还不含相交3-圈,或不含5-圈,或不含6-圈,则全染色数χ″(G)=Δ(G)+1。     

可平面图3可选择的一个充分条件

给G=(V,E)的每个顶点分配一个色列表L={L(v)|v∈V},若G有一个正常顶点染色φ,使得对每个顶点v∈V,都有φ(v)∈L(v),则称G是L可染的。若对G的每一个满足|L(v)|≥k,v∈V的L,G都是L可染的,则称G是k可选择的。本文通过权转移方法证明了每个不含4,6,8,10圈的可平面图是3可选择的。     

不含4圈的平面图的无圈边染色

如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用已有的关于平面图的结构性质,证明了不含4圈的2-连通平面图的无圈边色数不超过Δ(G)+11。     

无相邻三角形平面图的(4,1)~*-可选性

若对任一顶点给定k种颜色的列表,染色时每个顶点的颜色只能从自身的颜色列表中选择且每个顶点至多有d个邻点染相同的颜色,总存在图G的一个顶点的正常着色,则图G称为(k,d)*-可选色的.文章证明了每个无相邻三角形的平面图是(4,1)*-可选色的.     

点关联较少3-面的平面图的全染色

证明了对每点至多关联2个3-面的平面图，全染色猜想成立. 对每点至多关联2个3-面且Δ(G)≥8的平面图，有x_T(G)=Δ(G)+1.对每点至多关联[Δ(G)/2」个3-面且Δ(G)≥9的平面图，有x_T(G)=Δ(G)+1.     

关于图的星荫度的一个注

图G的曼荫度vas(G)定度为对G进行项点着色且使得G中同色顶点导出的子图的每个连通分支都为星时所需的最少色数,本文证明了平面图和外平面图的曼荫度的平凡上界事实上也是最好的上界.     

δ>2极大平面二分图间的关系

本文讨论δ>2极大平面二分图之间的关系,证明了 B_(mn)每一图可由其任一图经改边得到.