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

A Sufficient Condition for an IC-planar Graph to be of Class 1

图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是第一类图.

A proper edge k-coloring of a graph G is a mappingφ:E(G)→{1,2,…,k}such thatφ(x)≠φ(y)for any two adjacent edges x and y in G.The minimum k such that G has a proper edge k-coloring is the chromatic index,denoted byχ'(G).The well-known Vizing's theorem tells us thatχ'(G)=Δ(G)orΔ(G)+1 for every simple graph G.This theorem divides all graphs into two classes:Class 1 graphs haveχ'(G)=Δ(G);Class 2 graphs haveχ'(G)=Δ(G)+1.In this paper,we focus on the proper edge coloring of special 1-planar graphs.A graph is a 1-planar graph if it can be drawn in the plane so that each edge is crossed by at most one other edge,such a drawing is called a 1-planar embedding.For each crossing vertex w in a 1-plane graph,w is corresponding to two crossing edges which create w and a vertex setψ(w)of four endpoints of the two crossing edges.A 1-planar graph G is said to be an IC-planar graph ifψ(w)∩ψ(w')=∅for any two crossing vertices w and w'in a 1-planar embedding of G.By observing and analyzing the structures ofΔ-critical graphs and the graphs without adjacent chordal 6-cycles,we will prove that an IC-planar graph G withΔ(G)≥7 is of Class 1 if G contains no adjacent chordal 6-cycles.