最大度大于等于9的IC-平面图的线性荫度

图的线性荫度la(G)是指能够使得G的边集可以被划分成m个边不交的线性森林的最小的m。1-平面图是指一个图画在平面上使得每条边与其他边至多相交一次。IC-平面图是指1-平面图的任意两个交叉点所关联的交叉边的端点是互不相交的。本文证明了Δ(G)≥9的IC-平面图满足线性荫度猜想。

不含4-圈的IC-平面图的线性荫度

图G的边分解是指将G分解成子图G1, G2, . . . , Gm,使得E(G) = E(G1)∪ ···∪E(Gm),且对任意i ≠ j,有E(Gi) ∩ E(Gj ) = ∅。若一个森林的每个连通分支都是路,则称该森林为线性森林。 图G的线性荫度la(G)是指使得G可以边分解为m个线性森林的最小整数m。本文利用权转移方法证明了不含4-圈且∆(G) ≥ 9的IC-平面图G的线性荫度为。

几类IC-平面图的退化性

若图G的每一个子图H都有δ(H) ≤ k, 则称G是k-退化的. 根据不含k-圈(k ∈ {3, 5, 6})的平面图是3-退化的, 本文证明了不含k-圈的IC-平面图是4-退化的. 本文还进一步证明了3-圈与4-圈不相邻, 3-圈与5-圈不相邻或4-圈与4-圈不相邻的IC-平面图也是4-退化的. 同时, 本文给出了不含k-圈(k ∈ {3, 4, 5, 6})且4-正则的IC-平面图的例子。

IC-平面图的强边染色

IC-平面图是任意一条边至多被交叉一次且任意两条交叉边没有公共点的图.一个图的强边染色是一个正常边染色,使得距离至多为2的边得到不同的颜色.在这篇论文中,我们证明了每个Δ≥5且围长g≥7的IC-平面图可以使用6Δ+2种颜色强边染色.

IC-平面图的线性荫度

图G的边分解是指将G分解成子图G1,G2,...,Gm,使得E(G)=E(G_(1))∪…∪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的最大度.

无三角形IC-可平面图的线性2-荫度

设G为最大度为Δ的IC-可平面图。图G的线性2-荫度la_(2)(G)是将G分解为k个边不交森林的最小正整数k,其中森林的每个分支均为长至多为2的路。本文通过权转移方法研究了无三角形IC-可平面图的线性2-荫度,得到la_(2)(G)≤[△+1/2]+5。

IC-平面图为第一类图的一个充分条件

图G的一个正常k-边染色是指一个映射φ:E(G)→{1,2,…,k},使得任意两条相邻的边x,y∈E(G)满足φ(x)≠φ(y).使得G具有正常k-边染色的最小正整数k称为图G的边色数,记为χ'(G).著名Vizing定理证明每个简单图G的边色数χ'(G)要么等于最大度Δ(G)要么等于Δ(G)+1.这个定理将所有的图分成了两类:第一类图满足关系式χ'(G)=Δ(G),第二类图满足关系式χ'(G)=Δ(G)+1.本文主要讨论特殊1-平面图的正常边染色问题.1-平面图G是指G能够嵌入到平面上使得G的任意一条边最多被交叉一次.1-平面图G按照上述条件的一种画法称为G的一种1-平面嵌入.所以1-平面图中的每个交叉点w都是由两条边相交所得,从而每个交叉点w都对应着两条相交边,同时也对应着由这两条相交边的四个端点组成的集合ψ(w).如果1-平面图的一个1-平面嵌入中任意两个交叉点w和w'满足ψ(w)∩ψ(w')=∅,那么称此1-平面图为IC-平面图.在本文中,通过观察分析Δ-临界图和不含相邻弦6-圈的IC-平面图的结构,应用权值转移方法证明了任何最大度为7且不含相邻弦6-圈的IC-平面图G是第一类图.

度限制条件下的IC平面图类中轻弦4-圈的存在性

利用权转移方法证明每个最小度至少为5并且最小边度至少为11的IC-平面图含有一个最大度至多为11的弦4-圈。

具有度限制条件的IC平面图类中轻3-圈的存在性

利用权转移方法证明了每个最小度至少为5并且最小边度至少为11的IC-平面图G含有一个最大度max{d(u),d(v),d(w)}≤17的3-圈。

1-平面图及其子类的染色

如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果.

限制度的IC平面图中轻弦4-圈的权和

删去完全图k 4任意一条边所得的图称为弦4-圈.利用权转移方法讨论限制度的IC-平面图中轻弦4-圈的权和,证明每个最小度至少为5且最小边度至少为11的IC-平面图含有一个轻弦4-圈v 1v 2v 3v 4v 1,并证明具有该类限制度的IC-平面图中轻弦4-圈权和的上界小于等于37.

无4-圈的IC-可平面图的线性2-荫度

设G是最大度为Δ的IC-可平面图.图G的线性k-边染色是指G的一个映射φ:E(G)→{1,2,···,k}满足由染同一种颜色的边集导出的子图的连通分支均是长至多为2的路.图G的线性2-荫度是使G有一个线性k-边染色的最小正整数k.运用权转移方法研究了IC-可平面图的线性2-荫度,得到无4-圈的IC-可平面图的线性2-荫度的上界为[△+1/2]+3.

禁用C_(4)的IC-可平面图中C_(k)的最大个数

给定图G和H,如果图G不包含图H作为子图,则称图G是禁用H的.用ex_(ICP)(n,F,H)表示在所有禁用H且顶点数为n的IC-可平面图中,含与F同构的子图的最大个数.本文证明了对任意的k≥5,当n充分大时,有ex_(ICP)(n,C_(k),C_(4))=Θ(n^([k/3])).

不含相交三角形IC-可平面图的邻点可区别边染色

设φ为图G的l-正常边染色,C_(φ)(u)为G中所有与顶点u关联的边所染颜色的集合。如果对G的任意边uv,都有C_(φ)(u)与C_(φ)(v)不同,则称染色φ为G的l-邻点可区别边染色,简记为l-avd染色。使图G有l-avd染色的最小正整数l称为图G的邻点可区别边色数,记为χ_(a)′(G)。本文通过权转移方法研究不含相交三角形IC-正常可平面图G的邻点可区别边染色,得到χ_(a)′(G)≤max{Δ(G)+2,12}。

不含三角形的IC-可平面图的邻点可区别边染色

图G的k-邻点可区别边染色(简称k-avd染色)是图G的至多使用k个颜色的正常边染色,使得对G中任意相邻的顶点u,v,与u关联的边所染的颜色构成的集合不同于与v关联的边所染的颜色构成的集合.图G的邻点可区别边色数χ'_(a)(G)是G有k-avd染色的最小的整数k.张忠辅等人在[Appl.Math.Lett.,2002,15(5):623-626]中猜想对于任何阶至少为6的连通图G,都有χ'_(a)(G)≤Δ(G)+2.通过权转移方法,本文证明了对于任何Δ(G)≥10的不含三角形的连通IC-可平面图G,都有χ'_(a)(G)≤Δ(G)+2.

围长至少为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}.

三类超越可平面图的结构及其约束数

如果一个图可以嵌入在平面内使得每条边最多被交叉一次,则称该图为1-可平面图.如果一个图可以嵌入在平面内使得任何两个交叉不共享关联点,则称该图为IC-可平面图.如果一个图可以嵌入在平面内使得任何两个交叉最多共享一个关联点,则称该图为NIC-可平面图.1-可平面图,IC-可平面图与NIC-可平面图是三类重要的超越可平面图,它们在模块网络,社交网络和生物网络上有着重要的应用.图的约束数是为了使图的支配数严格增加所需要删除的最少的边数,它是衡量网络脆弱性的一个重要参数.本文考虑1-可平面图,IC-可平面图与NIC-可平面图的结构,并利用得到的结构定理证明了它们的约束数分别最多是13,11与12.