«Previous Article|Table of Contents|Next Article»

《南京师大学报（自然科学版）》[ISSN:1001-4616/CN:32-1239/N]

Issue:

2011年03期

Page:

19-24

Research Field:

数学

Publishing date:

Info

Title:

Edge Coloring of Planar Graphs With Δ=6 Without Short Cycles Contain Chords

Author(s):

Ni Weiping

School of Mathematics and Statistics,Zaozhuang University,Zaozhuang,277160,China

Keywords:

planar graph; edge coloring; maximum degree; cycle

PACS:

O157.5

DOI:

-

Abstract:

Let G be a planar graph of maximum degree Δ，G is said to be class 1 if χ’( G) = Δ and class 2 if χ’( G) = Δ + 1，where χ’( G) denotes the chromatic index of G． In 1965，Vizing proved that every planar graph of maximum degree at least eight is of class 1． By applying a Discharging method，we prove that every simple planar graph G with Δ = 6 is of class 1，if G does not contain chordal-k-cycles ( 4≤k≤7) ．

References:

［1］ Vizing V G． On an estimate of the chromatic index of a p-graph［J］． Diskret Analiz，1964，3 ( 1) : 25-30．
［2］ Vizing V G． Critical graphs with given chromatic class［J］． Diskret Analiz，1965，5 ( 1) : 9-17．
［3］ Sanders D P，Zhao Y． Planar graphs of maximum degree seven are class 1［J］． Combin Theory Ser B，2001，83( 2) : 201- 212．
［4］ Zhang L． Every planar with maximum degree 7 is of class 1［J］． Graphs Combin，2000， 16( 4) : 467-495．
［5］ Zhou G． A note on graphs of class 1［J］． Discrete Math，2003，263( 1 /3) : 339-345．
［6］ Bu Y，Wang W． Some sufficient conditions for a planar graph of maximum degree six to be class 1［J］． Discrete Math，2006， 306( 13) : 1 440-1 445．
［7］ Li X，Luo R． Edge coloring of embedded graphs with large girth［J］． Graphs Combin，2003， 19( 3) : 393-401．
［8］ Wang Weifan，Chen Yongzhu． A sufficient condition for a planar graph to be class 1［J］． Theoret Computer Sci，2007，385 ( 1 /3) : 71-77．

Memo

Memo:

-

Common functions

Last Update: 2011-09-15