图的可收缩性与其团复形的无圈性

图Ｇ的团复形是一个抽象复形，它的单形是Ｇ的团，用Ｃ（Ｇ）表示。一个复形Ｋ称为无圈的如果Ｈｑ（Ｋ）＝０（ｑ＞０），Ｈ０（Ｋ）Ｊ。Ｉｖａｓｈｃｈｅｎｋｏ（１９９４）证明了如果Ｇ是可收缩的，则Ｃ（Ｇ）是无圈的。在组合拓扑讨论班上（１９９８）。谢力同教授提出上述命题的逆命题是否成立。本文我们证明当Ｃ（Ｇ）是一个锥形或Ｃ（Ｇ）的维数小于等于２时。

平面图的无圈5-可选性

假设Φ是图G的一个顶点染色。如果任意两个相邻的点染不同颜色,且每个圈至少使用三种颜色,则称Φ是一个无圈染色。如果对于G的任意的k-列表配置L,G有一个无圈L-染色,则称G是无圈k-可选的。本文证明了3圈不与i(i=3,7,9)圈相邻和4圈不与j(3≤j≤6)圈相邻的平面图是无圈5-可选的。

A Cycle Theorem for Hamiltonian Graphs without K 1,3 *

Let G=(V, E) be a hamiltonian K 1.3 free graph such that d(x) |V| 2 and G is connected for some vertex x of G . Then G is pancyclic with a few number of exceptions.