本文選題：-平面圖 + 交叉點(diǎn)��； 參考：《山東大學(xué)學(xué)報(bào)(理學(xué)版)》2017年04期

【摘要】：若圖G能畫到平面上,且允許每條邊至多出現(xiàn)一個(gè)交叉點(diǎn),則圖G是1-平面圖。圖G的一個(gè)正常點(diǎn)染色是指存在一個(gè)頂點(diǎn)集到顏色集的映射φ:V(G)→{1,2,…,k},對(duì)于G中的任意兩個(gè)相鄰的點(diǎn)u和v,φ(u)≠φ(v)。圖G的一個(gè)k染色是指圖G能夠正常點(diǎn)染色所需的色數(shù)至少為k,圖G有一個(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, 鈥，

本文編號(hào)：2118483