不包含｛4，8，9｝－圈平面图结构的性质

方冬云

（莆田学院 数学系，福建 莆田 351100）

1 基本术语及符号［1］

图论一个偶对G＝（V，E）来定义图，其中V表示顶点的集合，E表示边的集合，如果图G中边的两个顶点是无序的，则称图G为无向图。一般图G＝（V，E）的顶点数用｜V｜表示，边的数目用｜E｜表示，如果｜V｜和｜E｜都是有限的，则称图G是有限无向图，如果图G既没有环也没有两条连杆连接同一对顶点，则称图是简单图，文中所研究的图均指的是有限简单无向图。有限简单无向图G中的顶点u和v，若边e＝uv∈E（G），则称u和v相邻，也称u和v是e的端点，u和v分别与e相关联，则称u为图G中的任一顶点，与顶点u关联的边数称为u的度数，记作dG（u）。

如果有限简单无向图G能画在曲面上，且除端点处之外任何两条边均不相交，则称图G被嵌入曲面上，如果图G可以被嵌入在平面上，称为是可平面图，已经被嵌入在平面上的图称为平面有限简单无向图。设u和v是图的顶点，图G的一条u－v途径（链）是有限非空的顶点和边交替序列W＝u0e1u2e3…un－1enun（u＝u0，v＝vn），其中与边ei（1≤i≤n）相邻的两顶点ui－1和ui正好是ei的两个端点，如果w上的顶点互不同的途径称为路记作Pi，u0，ui分别为Pi的起点和终点，起点和终点相同的路称为圈。

图G的一个k－染色是一个映射φ：V→｛1，…，k｝，使得φ（u）≠φ（v），其中uv∈E。这样的映射称图G为k－可染。如果G有一个k－染色，令H是图G的一个点导出子图，φ是H 的一个k－染色，若G有一个k－染色φ，且满足φ在H 上的限制正好是φ，则称φ是φ在图G上的一个延拓，或称φ可以延拓到图G上。

令C是图G的一个圈，分别记圈C内部和外部的点集为int（C）和ext（C）。显然，Int（C）＝G－ext（C）和Ext（C）＝G－int（C）是图G的两个点导出子图。连接一个圈上不相邻两点间的连线称为弦，注意，在C内部的C的弦属于Ext（C）。……