f-Colorings of Some Graphs of f-Class 1  

作　　者：Xia ZHANG Gui Zhen LIU 

机构地区：[1]College of Mathematics Science, Shandong Normal University, Ji'nan 250014, P. R. China [2]School of Mathematics and System Sciences, Shandong University, Ji'nan 250100, P. R. China [3]School of Mathematics and System Sciences, Shandong University, Ji'nan 250100, P. R. China

出　　处：《Acta Mathematica Sinica,English Series》2008年第5期743-748,共6页数学学报（英文版）

基　　金：NSFC (10471078,60673047);RSDP (20040422004);NSF of Hebei(A2007000002) of China

摘　　要：An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v V（G） at most f（v） times. The minimum number of colors needed to f-color G is called the f-chromatic index of G and is denoted by X′f（G）. Any simple graph G has the f-chromatic index equal to △f（G） or △f（G） ＋ 1, where △f（G） =max v V（G）{[d（v）/f（v）]}. If X′f（G） = △f（G）, then G is of f-class 1; otherwise G is of f-class 2. In this paper, a class of graphs of f-class 1 are obtained by a constructive proof. As a result, f-colorings of these graphs with △f（G） colors are given.An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v V（G） at most f（v） times. The minimum number of colors needed to f-color G is called the f-chromatic index of G and is denoted by X′f（G）. Any simple graph G has the f-chromatic index equal to △f（G） or △f（G） ＋ 1, where △f（G） =max v V（G）{[d（v）/f（v）]}. If X′f（G） = △f（G）, then G is of f-class 1; otherwise G is of f-class 2. In this paper, a class of graphs of f-class 1 are obtained by a constructive proof. As a result, f-colorings of these graphs with △f（G） colors are given.

关 键 词：simple graph EDGE-COLORING f-coloring classification of graphs f-chromatic index 

分 类 号：O24[理学—计算数学]