图的BB-染色

发布时间：2017-12-28 12:10

  本文关键词：图的BB-染色　出处：《浙江师范大学》2015年硕士论文　论文类型：学位论文

  更多相关文章： 平面图 BB-染色 生成树 圈

【摘要】：设V是由n(n0)个元素所形成的集合,V中的某些二元子集所形成的集合记作E.称有序对G=(V,E)是一个无向图,其中V中的元素称为图G的顶点,E中的元素称为图G的边.V称为图G的顶点集合,E称为图G的边集合.设图G的一个生成子图为H.(G,H)的一个BB-k-染色定义为映射φ:V(G)→{1,2,…,k},满足：1)当uv∈E(H)时,|φ(u)-φ(v)|≥2;2)当uvEE(G)\E(H)时,|φ(u)-φ(v)|≥1.称χb(G)=min{k|(G,H)是BB-k-可染的}为(G,H)的BB-色数.(G,H)的一个BB-L-染色是指存在(G,H)的一个BB-染色c,使得(?)v∈V(G),有c(v)∈L(v).若(G,H)存在一个BB-L-染色,则称(G,H)是BB-L-可染的.若对(G,H)的任意一个列表配置L,|L(v)|≥k,(G,H)都是BB-L-可染的,则称(G,H)是BB-k-可选的.称chBB(G,H)=min{k|(G,H)是BB-k-可选的}为(G,H)的BB-选择数.关于平面图的BB-染色,目前已有不少研究成果.在第二章,主要证明了若连通平面图G,G中3-圈与5-圈不相邻,则存在G的一棵生成树T,使得Xb(G,T)≤4.在第三章,主要证明了若连通平面图G,G中没有7-圈或8-圈或9-圈且不含相邻4-圈,则存在G的一棵生成树T,使得Xb(G,T)≤4.这些结果主要运用经典的Discharging方法,进一步拓展了平面图的BB-4-可染的若干充分条件.
[Abstract]:A V is composed of n (N0) formed a set of elements, the formation of V in some of the two element subset of the set denoted as E. ordered on G= (V, E) is an undirected graph, in which the elements in the V called the vertices of a graph G, E elements called map G side.V is called the vertex set of a graph G, E called G the edge set. A graph G is a spanning subgraph of H. (G, H) defined by a BB-k- staining for mapping Phi: V (G), {1,2,... ,k},婊¤冻锛，

本文编号：1345921