文献

J-GLOBAL ID：201802254071711342   整理番号：18A0226590

ISK4フリーグラフの彩色数

Chromatic Number of ISK4-Free Graphs

著者 (1件)： LE Ngoc Khang (ENS de Lyon, Lyon, FRA)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 33  号： 6  ページ： 1635-1646  発行年： 2017年 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 若し,グラフGが誘導された部分グラフとして,K₄の如何なる細分をも内包しなければ,GはISK4フリーであると言う。ISK4フリーグラフと{ISK4,三角形}フリーグラフの,彩色数に関する新しい上界を提案した。定理3(Gを{ISK4,三角形}フリーグラフとすれば,Χ(G)≦4である。)で見付けた境界は,予測2(若し,Gが{ISK4,三角形}フリーグラフであれば,Χ(G)≦3,である。)で述べたものに近いだけではなく,各層の単純構造は関心を惹くものである。著者等は,著者等の分類によって予測2に確定できると信じている。定理4(GをISK4フリーグラフとすれば,Χ(G)≦24,である。)に関して,若し,各層を念入りに調べて構造を簡素にすれば,著者等が見付けた境界24は若干改良できると考えているが,予測1(若し,GがISK4フリーグラフであれば,Χ(G)≦4,である。)で記述した境界に達するのは困難に見える。

シソーラス用語： *数値 ,  グラフ ,  *部分グラフ ,  限界 ,  グラフ理論 ,  三角形 ,  分割
準シソーラス用語： *フリーグラフ ,  *彩色数 ,  細分化 ,  上界 ,  単純グラフ

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

引用文献 (9件)：

• Bondy, J.A., Murty, U.S.R.: Graph theory, vol. 244. Springer, New York (2008)
• Chalopin, J., Esperet, L., Li, Z., Ossona de Mendez, P.: Restricted frame graphs and a conjecture of scott. Electron. J. Comb. 23(1), P1-30 (2016)
• Chudnovsky, M., Liu, C.H., Schaudt, O., Spirkl, S., Trotignon, N., Vuskovic, K.: Triangle-free graphs that do not contain an induced subdivision of k₄ are 3-colorable (2017). arXiv:1704.08104
• Gyárfás, A.: Problems from the world surrounding perfect graphs. Appl. Math. 19(3-4), 413-441 (1987)
• Kühn, D., Osthus, D.: Induced subdivisions in K_s,s-free graphs of large average degree. Combinatorica 24(2), 287-304 (2004)

タイトルに関連する用語 (2件)： グラフ ,  彩色数