论文部分内容阅读
对平面图G的边面染色，是指对图G的每条边和每个面染上一种颜色，使得相邻的边和面染不同的颜色；边面色数Xef（G）是对图G的进行边面染色的最小色数。对平面图G的完备染色，是指对的G每个顶点、每条边和每个面均染上一种颜色，使得相邻的顶点、边和面染不同的颜色；完备色数Xvef（G）是对图G的进行完备染色的最小色数。 给定平面图G=（V，E），若存在一个外边e∈E，使得G-e是一个外平面图（即图G-e中所有点都与其无界面相关联），则称G为几乎外平面图。 本文在对外平面图的性质进行深入探讨的基础上，讨论了几乎外平面图的边面染色和完备染色问题。我们证明了对任意几乎外平面图G，其边面色数必满足Xef（G）≤max{7，△（G）+1}，进而当G是2-连通且△（G）≥6时，有Xef（G）=△；而且其完备色数必满足Xvef（G）≤max{9，△（G）+2}，进而当G是2-连通且△（G）≥7时，有Xvef（G）=△+1。