文献

J-GLOBAL ID：201802285776993743   整理番号：18A0345489

数チェリーを持つグラフの適切に色付きされたおよびレインボーコピー【Powered by NICT】

Properly colored and rainbow copies of graphs with few cherries

著者 (2件)： Sudakov Benny (Department of Mathematics, ETH, 8092 Zurich, Switzerland) ,  Volec Jan (Department of Mathematics, ETH, 8092 Zurich, Switzerland)
資料名： Journal of Combinatorial Theory. Series B  (Journal of Combinatorial Theory. Series B)
巻： 122  ページ： 391-416  発行年： 2017年 
JST資料番号： E0780A  ISSN： 0095-8956  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Gは直線的に多くのチェリー(すなわち,3頂点上の経路)を含むn-頂点グラフとし,cは各頂点で各色は常にのみ多数回現れることをこのような完全グラフKnのエッジ彩色とする。1979では,ドラムカッタは,このような着色cはGの適切にカラーコピーを含む必要があると推測強形式,O(n 4/3)チェリーを持つグラフGに対してさえも保たれていることを示してこの推測を確立し,さらにチェリーの数にこの限界は定数倍まで可能な最良である。著者等は,また,全ての色は有界回数のように見えるKnの各辺彩色におけるこのようなGの虹コピーを見つけることができることを証明した。著者らの証明は,LuおよびSzekelyの枠組みをいくつかの付加的な見解と一緒にランダム全単射の空間における偏ったLovasz局所補題を用いた。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *グラフ ,  着色 ,  完全グラフ ,  発色 ,  *桜桃
準シソーラス用語： 補題 ,  有界 , 【Automatic Indexing@JST】

著者キーワード (4件)： Ramsey型問題 ,  レインボーと適切に色付け部分グラフ ,  スパンニング部分グラフ ,  局所補助定理

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (4件)： チェリー ,  グラフ ,  レインボー ,  コピー