本文選題：-平面圖 + 交叉點　； 參考：《山東大學學報(理學版)》2017年04期

【摘要】：若圖G能畫到平面上,且允許每條邊至多出現(xiàn)一個交叉點,則圖G是1-平面圖。圖G的一個正常點染色是指存在一個頂點集到顏色集的映射φ:V(G)→{1,2,…,k},對于G中的任意兩個相鄰的點u和v,φ(u)≠φ(v)。圖G的一個k染色是指圖G能夠正常點染色所需的色數(shù)至少為k,圖G有一個k染色又稱圖G是k-可染的。通過權(quán)轉(zhuǎn)移的方法證明了不含3圈和4圈的1-平面圖是5-可染的。
[Abstract]:If a graph G can be drawn to a plane and allows at most one intersection point for each edge, then G is a 1-planar graph. A normal point coloring of a graph G is a mapping 蠁: v (G) {1 / 2, 鈥，

本文編號：2118483