文献

J-GLOBAL ID：201702269934031975   整理番号：17A0963096

所定の集合の1実現である最小一様な色有界の超グラフ

The Smallest Uniform Color-Bounded Hypergraphs Which are One-Realizations of a Given Set

著者 (4件)： DIAO Kefeng (Linyi Univ., Shandong, CHN) ,  LU Fuliang (Linyi Univ., Shandong, CHN) ,  VOLOSHIN Vitaly (Troy Univ., AL, USA) ,  ZHAO Ping (Linyi Univ., Shandong, CHN)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 33  号： 4  ページ： 869-883  発行年： 2017年 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： グラフの彩色問題は理論と実用の面で組み合わせ問題として関心が集まっている。グラフと超グラフの既存の彩色は,端部の無いものは単色性であることとし,その双対問題は超グラフ問題の共通彩色と呼ばれて,端部の無いものを多色性(レインボー)とした。色有界超グラフは頂点集合Xと端部集合ε={E₁,E₂,...,E_m}を有し,i=1,2,...,mに関して,整数s_i,とt_i(1≦s_i≦t_i≦|E_i|)とする超グラフである。若し,各1≦i≦mに関して,端部E_iに生じる彩色数が,s_i≦|φ(E_i)|≦t_iを満たせば,頂点彩色φは適切である。本稿では,[r/2]<t≦r-2,及びmax(S)≧3r/2,のときの事例に関して,Sの1実現であるr一様な色有界超グラフΗ=(X,ε,2,t)の頂点の最小数を決定した。

シソーラス用語： 集合 ,  *限界 ,  均一性 ,  *彩色問題 ,  双対問題 ,  頂点 ,  端部 ,  *超グラフ ,  グラフ理論
準シソーラス用語： 一様性 ,  *有界

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

引用文献 (29件)：

• Axenovich, M., Kündgen, A.: On a generalized anti-Ramsey problem. Combinatorica 21, 335-349 (2001)
• Bujtás, C., Tuza, Z.: Color-bounded hypergraphs, I: general results. Discret. Math. 309, 4890-4902 (2009)
• Bujtás, C., Tuza, Z.: Color-bounded hypergraphs, II: interval hypergraphs and hypertrees. Discret. Math. 309, 6391-6401 (2009)
• Bujtás, C., Tuza, Z.: Color-bounded hypergraphs, III: model comparison. Appl. Anal. Discret. Math. 1, 36-55 (2007)
• Bujtás, C., Tuza, Z.: Color-bounded hypergraphs, IV: stable colorings of hypertrees. Discret. Math. 310, 1463-1474 (2010)

タイトルに関連する用語 (4件)： 集合 ,  色 ,  有界 ,  グラフ