Factors and induced subgraphs

本研究的目的是探讨图的因子与禁止子图之间的关系。在研究期间，我们取得了一些成果。其中部分列举如下：Sumner（1974）证明了每一个连通的K_<1,3>偶阶自由图都有一个1因子。我们研究了这种类型的逆，证明了如果每一个偶阶的连通无H图都有一个1因子，那么H要么同构于K_<1,2>，要么同构于K_<1,3>。这个结果表明，本质上K_<1,3>是唯一一个通过禁止它来强制1因子存在的图2。证明了如果每一个连通的偶阶{H_1，H_2}图都有一个1因子，那么H_1或H_2是同构于K_<1,2>或K_<1,3>的。这个结果表明，如果我们禁止一对图强制存在一个1因子，那么这对图中总有一个是冗余的。另一方面，我们发现如果我们禁止三个图，那么情况就会改变。我们找到了一个三层{H_1，H_2,H_3}，使得每一个连通的偶阶{H_1，H_2，H_3}自由图都有一个1因子，并且它们都不同构于K_<1,3>的子图。这个结果表明，有一个非冗余的三组图，迫使一个1因子的存在。此外，我们还发现了无穷多个这样的三元组。作为总结，我们完全刻画了一组禁止子图，当该集合的阶数最多为3时，该集合强制存在一个1因子。

The purpose of this research was to investigate the relationship between factors of graphs and forbidden subgraphs. During the research period, we have obtained a number of results. Some of them are listed as follows ;1.Sumner (1974) has proved that every connected K_<1,3>-free graph of even order has a 1-factor. We investigated the converse of this type, and proved that if every connected H-free graph of even order has a 1-factor, then H is isomorphic to either K_<1,2> or K_<1,3>. This result says that essentially K_<1,3> is the only graph that forces the existence of a 1-factor by forbidding it.2.We proved that if every connected {H_1,H_2}-graph of even order has a 1-factor, then wither H_1 or H_2 is isomorphic to K_<1,2> or K_<1,3>. This result says that if we forbid a pair of graphs to force the existence of a 1-factor, then one of the pair always becomes redundant.3.On the other hand, we found that if we forbid three graphs, then the situation changes. We found a triple {H_1,H_2,H_3} such that every connected {H_1,H_2,H_3}-free graph of even order has a 1-factor, and none of them are isomorphic to a subgraph of K_<1,3>. This result suggests that there are a non-redundant triple of graphs which force the existence of a 1-factor. Moreover, we found infinitely many such triple.As a summary, we completely characterized a set of forbidden subgraphs forcing the existence of a 1-factor when the order of the set is at most three.