On subgraphs and subposets of bound graphs

关于有界图的子图和子集

• 批准号: 18540139
• 负责人: TSUCHIYA Morimasa
• 金额: $ 2.46万
• 依托单位: Tokai University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18540139/
• 关键词: graph theory; poset; upper bound graph; double bound graph; forbidden subgraph; forbidden subposet; semi bound graphs; upper bound grap; k-tree; semi bound graph

We consider upper bound graphs and double bound graphs in terms of induced subgraphs and subposets. We also deal with the relations between induced subgraphs and subposets of bound graphs in terms of clique covers.Based on properties of clique covers of double bound graphs, we deal with properties on maximal posets and minimal posets of a poset family with same semi bound graph. We obtain of the diameter and the radius of the family of posets with same semi bound graph.We also consider k-trees in terms of leafages. We show that there exists a k-tree for a given number of leafages.We deal with properties on principal order ideals and intervals. Using these properties, we consider families of cliques on forbidden subgraphs. We obtain characterizations of some kinds of subfamily of upper bound graphs in terms of forbidden upper bound subgraphs. For example, star n-gons are forbidden upper bound subgraphs of upper bound chordal graphs. 2K_2 is a forbidden upper bound subgraphs of upper bound split graphs. For a graph G, G and its complement are Meyniel graphs if and only if G does not contain C_5 , P_5 and the house graph as induced subgraphs.

我们利用导出子图和子集来考虑上界图和双界图。在团覆盖的基础上，讨论了具有相同半有界图的偏序集族的极大偏序集和极小偏序集的性质。我们得到了具有相同半有界图的偏序集族的直径和半径，并用叶的形式讨论了k-树。我们证明了对于给定数量的叶子，存在一棵k-树。我们讨论了主序理想和区间的性质。利用这些性质，我们考虑了禁子图上的团族。利用禁止上界子图给出了几类上界图子族的刻画。例如，星n-角是上界弦图的禁止上界子图。2K_2是上界分裂图的一个禁止上界子图。对于图G，G及其补图是Meyniel图当且仅当G不包含C_5、P_5和House图作为导出子图。

项目成果

On the Enumeration of Bipartite Minimum Edge Colorings

关于二分最小边着色的枚举

• 发表时间: 2006
• 期刊: Proceedings of a Conference in Memory of Claude Berge, Trends in Mathematics, Graph Theory in Paris
• 作者: Yasuko Matsui;Takeaki Uno
• 通讯作者: Takeaki Uno

On intersection graphs and its applications

论交集图及其应用

• 作者: Morimasa;Tsuchiya
• 通讯作者: Tsuchiya

A note on chordal bound graph sand posets

关于弦约束图沙偏序集的注记

• 发表时间: 2008
• 期刊: Discrete Mathematics 308
• 作者: Morimasa Tsuchiya;Kenjiro Ogawa;Shin-ichi Iwai
• 通讯作者: Shin-ichi Iwai

On posets with double bound graphs which contain a star graph as an induced subgraph

在具有双界图的偏序集上，其中包含星图作为诱导子图

• 发表时间: 2007
• 作者: Morimasa Tsuchiya;Kenjiro Ogawa;Satoshi Tagusari
• 通讯作者: Satoshi Tagusari

Intersection graphとその応用について

关于交集图及其应用

• 发表时间: 2006
• 作者: Masao;Hara;Masahiko;Murakami;Seiichi;Tani;Makoto;Yamamoto;土屋 守正
• 通讯作者: 土屋 守正