Forbidden pairs with a common graph generating almost the same sets

Shuya Chiba, Michitaka Furuyal, Jun Fujisawa, Hironobu Ikarashi

研究成果: Article査読


Let H be a family of connected graphs. A graph G is said to be H-free if G does not contain any members of H as an induced subgraph. Let F(H) be the family of connected H-free graphs. In this context, the members of H are called forbidden subgraphs. In this paper, we focus on two pairs of forbidden subgraphs containing a com- mon graph, and compare the classes of graphs satisfying each of the two forbidden subgraph conditions. Our main result is the following: Let H1;H2;H3be connected graphs of order at least three, and suppose that H1 is twin-less. If the symmetric difference of F(fH1;H2g) and F(fH1;H3g) is finite and the tuple (H1;H2;H3) is non-trivial in a sense, then H2and H3are obtained from the same vertex-transitive graph by successively replacing a vertex with a clique and joining the neighbors of the original vertex and the clique. Furthermore, we refine a result in [Combin. Probab. Comput. 22 (2013) 733-748] concerning forbidden pairs.

ジャーナルElectronic Journal of Combinatorics
出版ステータスPublished - 2017 4月 13

ASJC Scopus subject areas

  • 理論的コンピュータサイエンス
  • 幾何学とトポロジー
  • 離散数学と組合せ数学
  • 計算理論と計算数学
  • 応用数学


「Forbidden pairs with a common graph generating almost the same sets」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。