文献

J-GLOBAL ID：201802251603524030   整理番号：18A0328148

単語表現可能グラフ上の新しい結果【Powered by NICT】

New results on word-representable graphs

著者 (4件)： Collins Andrew (Mathematics Institute, University of Warwick, Coventry, CV4 7AL, UK) ,  Kitaev Sergey (Department of Computer and Information Sciences, University of Strathclyde, Glasgow, G1 1XH, UK) ,  Lozin Vadim V. (Mathematics Institute, University of Warwick, Coventry, CV4 7AL, UK) ,  Lozin Vadim V. (DIMAP, University of Warwick, Coventry, CV4 7AL, UK)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 216  号： P1  ページ： 136-141  発行年： 2017年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 文字xおよびyは,(x , y)∈Eは各x≠yの場合にのみWの交互するようアルファベットV以上の単語Wが存在するならば,グラフG=(V , E)単語表現可能。単語表現可能グラフの集合は,いくつかの重要な,よく研究されたグラフ族を一般化し,円グラフ,比較可能性グラフ,3色色付け可能グラフ,高々3の頂点次数のグラフ,など。Halldorssonら(2011)からの未解決の問題に答えることにより,本論文では,最も4で頂点次数の全てのグラフは単語表現可能なことを示した。この結果を組み合わせたいくつかの既知の事実とは,n頂点単語表現可能グラフの数は2N23+O(n 2)であることを導いた。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 着色 ,  *単語 ,  *グラフ
準シソーラス用語： 次数 , 【Automatic Indexing@JST】

著者キーワード (3件)： 半推移的配向 ,  グラフの遺伝特性 ,  遺伝特性の速度

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

タイトルに関連する用語 (3件)： 単語 ,  表現 ,  グラフ