文献

J-GLOBAL ID：201802236525620743   整理番号：18A0226575

閉曲面上の二分多面体マップは,僅かの例外を持って特徴ある3種の彩色が可能である。

Bipartite Polyhedral Maps on Closed Surfaces are Distinguishing 3-Colorable with Few Exceptions

著者 (2件)： NEGAMI Seiya (Yokohama National Univ., Yokohama, JPN) ,  TUCKER Thomas W. (Colgate Univ., NY, USA)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 33  号： 6  ページ： 1443-1450  発行年： 2017年 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 若し,恒等マップが色を保持する以外に自己同型写像が無いように,閉曲面が固有のk色を持つならば,閉曲面上のマップは,特徴のあるk種の彩色が可能であると言われている。3連結性の代わりにマップの「多面体性」を前提として,一般表面に関する本稿での定理1(3立方体Q₃,又は,その放射グラフR(Q₃)でなければ,連結二分平面グラフは特徴のある3色の彩色が可能であり,それは特徴有る4種の彩色が可能である。)を一般化する必要がある。若し,各面が閉路によって有界な2胞体であって,若し,2面が最大1つの頂点で対合するか,1つの端部に沿っていれば,閉曲面上のマップM(G)は多面体と言われる。若し,M(G)が多面体であれば,基礎グラフGが3連結であることを確認するのは容易である。二分基礎グラフを持った多面体マップは,若し,18個を超す頂点を持っていれば,特徴ある3種による彩色が可能である。

シソーラス用語： *閉曲面 ,  多面体 ,  *彩色問題 ,  平面グラフ ,  閉路 ,  同形写像 ,  *写像 ,  部分グラフ
準シソーラス用語： 自己同形写像 ,  二分グラフ

分類 (1件)： 集合論  (AB10000I)

引用文献 (11件)：

• Collins, K.L., Trenk, A.: The distinguishing chromatic number. Electron. J. Combin. 13(1), R16 (2006)
• Fijavž, G., Negami, S., Sano, T.: 3-Connected planar graphs are 5-distinguishing colorable with two exceptions. Ars Mathematica Contemporanea 4(1), 165-175 (2011)
• Fijavž, G., Negami, S., Sano, T.: Distinguishing colorings of 3-connected planar graphs with five colors. Yokohama Math. J. 61, 57-65 (2011)
• Negami, S.: Uniqueness and faithfulness of embedding of toroidal graphs. Discrete Math. 44, 161-180 (1983)
• Negami, S., Sakurai, S.: Distinguishing chromatic numbers of planar graphs. Yokohama Math. J. 55, 179-188 (2010)

タイトルに関連する用語 (4件)： 閉曲面 ,  多面体 ,  マップ ,  彩色