|Table of Contents|

The Sufficient Conditions on 3-Colorable Plane Graphs(PDF)

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

Issue:
2011年03期
Page:
13-18
Research Field:
数学
Publishing date:

Info

Title:
The Sufficient Conditions on 3-Colorable Plane Graphs
Author(s):
Zhao Chunhong1; 2; Dong Wei1; 3
1.School of Mathematical Sciences,Nanjing Normal University,Nanjing 210046,China
Keywords:
plane graph;  cycle;  coloring
PACS:
O157.5
DOI:
-
Abstract:
This paper proveed the following sufficient conditions on 3-colorable plane graphs: ( 1) Let G be a plane graph with neither cycles of length from 4 to 6 nor triangles of distance less than two． Furthermore， if every 7-cycles of G is adjacent to at most one triangle， then G is 3-colorable; ( 2) Every plane graph with neither cycles of length 4，5 nor cycles of length 6 and 7 adjacent to cycles of length less than 8 is 3-colorable．

References:

［1］ Bondy J A，Murty U S R． Graph Theory With Applications［M］． New York: Macmillan Ltd Press，1976．
［2］ Abbott H L，Zhou B． Om small faces in 4-critical graphs［J］． Ars Combin，1991，32: 203-207．
［3］ Borodin O V，Glebov A N，Raspaud A，et al． Planar graphs without cycles of length from 4 to 7 are 3-colorable［J］． J Combin Theroy Ser B，2005，93: 303-311．
［4］ Xu B． On 3-colorable plane graphs without 5-and 7-cyclesm［J］． J Combin Thery Ser B，2006，96: 958-963．

Memo

Memo:
-
Last Update: 2011-09-15