【摘要】：如果圖G可以嵌入在平面上,使得每條邊最多被交叉1次,則稱其為1-可平面圖,該平面嵌入稱為1-平面圖.由于1-平面圖G中的交叉點是圖G的某兩條邊交叉產生的,故圖G中的每個交叉點c都可以與圖G中的四個頂點(即產生c的兩條交叉邊所關聯(lián)的四個頂點)所構成的點集建立對應關系,稱這個對應關系為θ.對于1-平面圖G中任何兩個不同的交叉點c_1與c_2(如果存在的話),如果|θ(c_1)∩θ(c_2)|≤1,則稱圖G是NIC-平面圖;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,則稱圖G是IC-平面圖.如果圖G可以嵌入在平面上,使得其所有頂點都分布在圖G的外部面上,并且每條邊最多被交叉一次,則稱圖G為外1-可平面圖.滿足上述條件的外1-可平面圖的平面嵌入稱為外1-平面圖.現(xiàn)主要介紹關于以上四類圖在染色方面的結果.
[Abstract]:If a graph G can be embedded in a plane so that each edge is crossed at most once, then it is called a 1-planar graph, and the plane embedding is called a 1-planar graph. Because the intersection points in 1-planar graph G are generated by the intersection of two edges of graph G. Therefore, each intersection point c in graph G can establish a corresponding relation with the set of points formed by four vertices in graph G (that is, four vertices associated with two cross edges of c), and this corresponding relation is called 胃. For any two different intersections of 1- plane graph G, c _ S _ 1 and C _ S _ 2 (if there is any), if 胃 (c _ 1) class 胃 (c ~ 2) class 胃 (c2) 鈮，

本文編號：2236365