【摘要】：如果圖G可以嵌入在平面上,使得每條邊最多被交叉1次,則稱其為1-可平面圖,該平面嵌入稱為1-平面圖.由于1-平面圖G中的交叉點(diǎn)是圖G的某兩條邊交叉產(chǎn)生的,故圖G中的每個(gè)交叉點(diǎn)c都可以與圖G中的四個(gè)頂點(diǎn)(即產(chǎn)生c的兩條交叉邊所關(guān)聯(lián)的四個(gè)頂點(diǎn))所構(gòu)成的點(diǎn)集建立對(duì)應(yīng)關(guān)系,稱這個(gè)對(duì)應(yīng)關(guān)系為θ.對(duì)于1-平面圖G中任何兩個(gè)不同的交叉點(diǎn)c_1與c_2(如果存在的話),如果|θ(c_1)∩θ(c_2)|≤1,則稱圖G是NIC-平面圖;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,則稱圖G是IC-平面圖.如果圖G可以嵌入在平面上,使得其所有頂點(diǎn)都分布在圖G的外部面上,并且每條邊最多被交叉一次,則稱圖G為外1-可平面圖.滿足上述條件的外1-可平面圖的平面嵌入稱為外1-平面圖.現(xiàn)主要介紹關(guān)于以上四類圖在染色方面的結(jié)果.
[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) 鈮，

本文編號(hào)：2236365