文献

J-GLOBAL ID：201902281831268094   整理番号：19A1474535

頂点彩色グラフのためのErdos-Gallai型定理

An Erdoes-Gallai type theorem for vertex colored graphs

著者 (5件)： Salia Nika (Central European University, Budapest, Hungary) ,  Salia Nika (Alfred Renyi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary) ,  Tompkins Casey (Alfred Renyi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary) ,  Zamora Oscar (Central European University, Budapest, Hungary) ,  Zamora Oscar (Universidad de Costa Rica, San Jose, Costa Rica)
資料名： Graphs and Combinatorics (Web)  (Graphs and Combinatorics (Web))
巻： 35  号： 3  ページ： 689-694  発行年： 2019年 
JST資料番号： U1590A  ISSN： 0911-0119  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 奇数サイクルのフリー超グラフを調査すると同時に,GyoriとLemonsはP_kフリーグラフに関するErdosとGallaiの古典的定理の彩色版を導入した。彼らは,適切な頂点彩色を有しかつ異なる色の境界頂点を含んで長さ2k+1の経路を持たない任意のグラフGでは,多くても2knのエッジを持つことを証明した。著者らは,ErdosとGallaiの元の鋭い上界であるknがこれらの問題に対して成り立つことも示した。また,木に対するこの問題のある判を紹介して,Erdos-Sos予測の一般化を提示した。Copyright 2019 The Author(s) Translated from English into Japanese by JST.

シソーラス用語： *彩色問題 ,  グラフ理論 ,  *超グラフ ,  木【グラフ】 ,  集合 ,  極値 ,  長さ
準シソーラス用語： *グラフ彩色 ,  経路長 ,  頂点被覆

著者キーワード (5件)： 極値 ,  パス ,  サイクル ,  樹木 ,  頂点着色

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

タイトルに関連する用語 (4件)： 頂点 ,  彩色 ,  グラフ ,  定理