文献

J-GLOBAL ID：201702246069652127   整理番号：17A0963089

禁止構造を持った平面グラフの(4,2)選択可能性

(4,2)-Choosability of Planar Graphs with Forbidden Structures

著者 (11件)： BERIKKYZY Zhanar (Iowa State Univ., IA, USA) ,  COX Christopher (Carnegie Mellon Univ., PA, USA) ,  DAIRYKO Michael (Iowa State Univ., IA, USA) ,  HOGENSON Kirsten (Colorado Coll., CO, USA) ,  KUMBHAT Mohit (Univ. Nevada, NV, USA) ,  LIDICKY Bernard (Iowa State Univ., IA, USA) ,  MESSERSCHMIDT Kacy (Iowa State Univ., IA, USA) ,  MOSS Kevin (Iowa State Univ., IA, USA) ,  NOWAK Kathleen (Pacific Northwest National Lab., WA, USA) ,  PALMOWSKI Kevin F. (Iowa State Univ., IA, USA) ,  STOLEE Derrick (Microsoft, NC, USA)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 33  号： 4  ページ： 751-787  発行年： 2017年 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 分割を使った4選択可能性に焦点を定めた。Kratochvil等(参考文献9)は全ての平面グラフは(4,1)選択可能であると証明し,一方で,Voigt(参考文献12)は(4,3)選択可能でない平面グラフが存在することを実証した。全ての平面グラフが(4,2)選択可能かどうかは知られていない。4選択可能性を考慮した幾つかの研究結果がある。若し,部分グラフの各々が最大k次数の頂点を持っていればグラフはk退化である。Eulerの公式は3個の閉路を持たない平面グラフは3退化であり,従って4選択可能であることを暗示している。この結果と同様のものを併せて,本稿中に定理4としてまとめた。この定理4に関して,一致した(chorded)l閉路は,非連続頂点の2つを連結した付加的な端部を持ったl閉路であることに注目した。一致したl閉路は1つの付加端部を持ったl閉路である。若し平面グラフが一致したl閉路を包含しなければ,各l∈{5,6,7}に関して,平面グラフは(4,2)選択可能であることを実証した。

シソーラス用語： *平面グラフ ,  部分グラフ ,  閉路 ,  端部 ,  *選択性 ,  恒等式 ,  *構造 ,  行為
準シソーラス用語： Eulerの公式 ,  *禁止

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

引用文献 (15件)：

• Alon, N., Tarsi, M.: Colorings and Orientations of Graphs. Combinatorica 12(2), 125-134 (1992). doi:10.1007/BF01204715
• Borodin, O.V.: Colorings of Plane Graphs: A Survey. Discret. Math. 313(4), 517-539 (2013). doi:10.1016/j.disc.2012.11.011
• Borodin, O.V., Ivanova, A.O.: Planar Graphs Without Triangular 4-Cycles are 4-Choosable. Sib. Élektron. Mat. Izv. 5, 75-79 (2008)
• Choi, I., Lidický, B., Stolee, D.: On Choosability with Separation of Planar Graphs with Forbidden Cycles. J. Graph Theory 81(3), 283-306 (2016). doi:10.1002/jgt.21875
• Cranston, D.W., West, D.B.: An Introduction to the Discharging Method via Graph Coloring. Discret. Math. 340(4), 766-793 (2017). doi:10.1016/j.disc.2016.11.022

タイトルに関連する用語 (3件)： 禁止 ,  平面グラフ ,  選択可能