不含 3-圈平面图的线性染色＊

王 侃

(浙江师范大学数理与信息工程学院,浙江金华 321004)

0 引 言

本文所考虑的图都是简单图.用 V(G),E(G),Δ(G)和δ(G)分别表示图 G的顶点集、边集、最大度和最小度.G的围长 g(G)是指 G中最短圈的长度.

图 G的一个正常染色是从顶点集合 V(G)到颜色集合{1,2,…,k}的一个映射,使得任意 2个相邻的顶点染不同的颜色;图G的一个线性 k-染色是一个正常染色,使得染任意 2种颜色的顶点集合导出的子图是一些点不交的路的并;图 G的线性色数 lc(G)定义为 G的所有线性 k-染色中最小的 k值.

文献[1]首先研究了图的线性染色,证明了任意图 G的线性色数满足圈染色是 G的一个正常染色,使得染任意 2种颜色的顶点集合导出的子图是一个森林.无圈染色的概念是由 Grünbaum[2]提出的.这方面的研究可参阅文献[2-5].

2008年,Esperet等[6]把线性染色的概念推广到线性选择性,他们研究了树、格子图、完全二部图、平面图、外平面图、最大度为 3或 4的图以及有较小最大平均度的图的线性选择数.

定理 1[6]设 G是一个平面图,则

定理 2[7]设 G是一个平面图,则

1)若存在一个有序对 (Δ,g)∈{(13,7),(7,9),(5,11),(3,13)},使得Δ(G)≥Δ,g(G)≥g,那么

本文考虑围长至少为 4的平面图的线性染色,得到如下的结果:

定理 4 设M≥5是一个正整数,G是一个Δ(G)≤M且没有 3-圈的平面图,则

1 基本概念

对于一个平面图 G,用 F(G)表示它的面集合.对∀f∈F(G),若 u1,u2,…,un是 f边界上依序排列的顶点,则记 f=[u1u2…un],注意到点的重复出现是允许的.面的度是指它的边界上边的条数,其中割边被计算 2次.对∀x∈V(G)∪F(G),用 dG(x)表示 G中 x的度.在不产生混淆的情况下,可以用 d(x)代替 dG(x).一个度数为 k的顶点 (面)被称为 k-点……