文献

J-GLOBAL ID：202002219503490761   整理番号：20A1019337

完全7彩色可能な最大次数6の平面グラフに対する十分条件【JST・京大機械翻訳】

A Sufficient Condition for Planar Graphs of Maximum Degree 6 to be Totally 7-Colorable

著者 (2件)： Zhu Enqiang ( Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China) ,  Rao Yongsheng ( Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China)
資料名： Discrete Dynamics in Nature and Society  (Discrete Dynamics in Nature and Society)
巻： 2020  ページ： Null  発行年： 2020年 
JST資料番号： W2228A  ISSN： 1026-0226  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： イギリス (GBR)  言語： 英語 (EN)

抄録/ポイント： グラフの全k彩色は,2つの隣接または入射要素が同じ色を受け取らないような頂点とエッジへのk色の割当である。全着色予測(TCC)状態は,あらゆる単純グラフGが全[数式:原文を参照]-着色を有し,そこでは[数式:原文を参照]がGの最大度であることを示した。この予測は,少なくとも7以上の最大次数をもつ平面グラフに対して確認された。すなわち,TCCの唯一のオープンケースは,最大次数6のものである。いくつかの制約を有する[数式:原文を参照]または[数式:原文を参照]のあらゆる平面グラフGは,全[数式:原文を参照]-着色を有することが知られている。特に,(ShenとWang,2009)において,著者らは,最大6と4サイクルのないすべての平面グラフが,全体の7-着色を持つことを証明した。本論文では,すべての6頂点が2つの隣接する4サイクルまたは3サイクルのサイズの[数式:原文を参照]に対して,いくつかの[数式:原文を参照]に対して入射しない場合に,最大次数6のすべての無次元平面グラフが全体的に7色可能であることを示すことにより,この結果を改善した。Copyright 2020 Enqiang Zhu and Yongsheng Rao. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *平面グラフ ,  着色 ,  *発色 ,  十分条件 ,  4サイクル
準シソーラス用語： 単純グラフ , 【Automatic Indexing@JST】

分類 (2件)： グラフ理論基礎  (IA02020S) ,  集合論  (AB10000I)

引用文献 (13件)：

• J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, New York, NY, USA, 2008.
• M. Behzad, Graph and Their Chromatic numbers, Michigan State University, East Lansing, MI, USA, 1965, Doctoral thesis.
• V. G. Vizing, "Some unsolved problems in graph theory," Russian Mathematical Surveys, vol. 23, no. 6, pp. 125-141, 1968.
• A. V. Kostochka, "The total chromatic number of any multigraph with maximum degree five is at most seven," Discrete Mathematics, vol. 162, no. 1-3, pp. 199-214, 1996.
• D. P. Sanders, Y. Zhao, "On total 9-coloring planar graphs of maximum degree seven," Journal of Graph Theory, vol. 31, pp. 315-319, 1999.

タイトルに関連する用語 (4件)： 彩色 ,  次数 ,  平面グラフ ,  十分条件