本文關(guān)鍵詞：圖的BB-染色　出處：《浙江師范大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 平面圖 BB-染色 生成樹 圈

【摘要】：設(shè)V是由n(n0)個(gè)元素所形成的集合,V中的某些二元子集所形成的集合記作E.稱有序?qū)=(V,E)是一個(gè)無(wú)向圖,其中V中的元素稱為圖G的頂點(diǎn),E中的元素稱為圖G的邊.V稱為圖G的頂點(diǎn)集合,E稱為圖G的邊集合.設(shè)圖G的一個(gè)生成子圖為H.(G,H)的一個(gè)BB-k-染色定義為映射φ:V(G)→{1,2,…,k},滿足：1)當(dāng)uv∈E(H)時(shí),|φ(u)-φ(v)|≥2;2)當(dāng)uvEE(G)\E(H)時(shí),|φ(u)-φ(v)|≥1.稱χb(G)=min{k|(G,H)是BB-k-可染的}為(G,H)的BB-色數(shù).(G,H)的一個(gè)BB-L-染色是指存在(G,H)的一個(gè)BB-染色c,使得(?)v∈V(G),有c(v)∈L(v).若(G,H)存在一個(gè)BB-L-染色,則稱(G,H)是BB-L-可染的.若對(duì)(G,H)的任意一個(gè)列表配置L,|L(v)|≥k,(G,H)都是BB-L-可染的,則稱(G,H)是BB-k-可選的.稱chBB(G,H)=min{k|(G,H)是BB-k-可選的}為(G,H)的BB-選擇數(shù).關(guān)于平面圖的BB-染色,目前已有不少研究成果.在第二章,主要證明了若連通平面圖G,G中3-圈與5-圈不相鄰,則存在G的一棵生成樹T,使得Xb(G,T)≤4.在第三章,主要證明了若連通平面圖G,G中沒(méi)有7-圈或8-圈或9-圈且不含相鄰4-圈,則存在G的一棵生成樹T,使得Xb(G,T)≤4.這些結(jié)果主要運(yùn)用經(jīng)典的Discharging方法,進(jìn)一步拓展了平面圖的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},婊¤凍錛，

本文編號(hào)：1345921