机构名称：
¥ 1.0
我们遵循 [9, 13] 中的符号。设 G 为图。对于 V(G) 的非平凡划分 (A,B)，1如果路径 P 的一端在 A 中而另一端在 B 中，则我们称路径 P 为 A - B 路径。设 P 为图 G 中的一条路径。设 | P | 为 P 中的边数。如果 | P | 为偶数（分别为奇数），则我们称 P 为偶数（分别为奇数）。设 C 为按循环顺序具有顶点 v 0 ，v 1 ，...，vt − 1 的环。设 C i,j 表示 C 的子路径 vivi +1...vj，其中索引取自加法群 Z t 。设 H 为 G 的子图。如果顶点 v ∈ V ( G ) − V ( H ) 在 G 中与 V ( H ) 中的某个顶点相邻，则我们称 H 和顶点 v ∈ V ( G ) − V ( H ) 在 G 中相邻。设 NG ( H ) = S v ∈ V ( H ) NG ( v ) − V ( H ) 且 NG [ H ] = NG ( H ) ∪ V ( H )。对于 S ⊆ V ( G )，如果 V ( G ′ ) = ( V ( G ) − S ) ∪{ s } 且 E ( G ′ ) = E ( G − S ) ∪{ vs : v ∈ V ( G ) − S 与 G 中的 S 相邻 } ，我们称图 G ′ 是通过将 S 收缩为顶点 s 而从 G 得到的。如果 G − v 包含至少两个分支，则连通图 G 的顶点 v 是 G 的割顶点。 G 中的块 B 是 G 的最大连通子图，使得不存在 B 的割顶点。注意块是孤立顶点、边或2连通图。G 中的端块是 G 中最多包含一个 G 的割顶点的块。如果 G 是图并且 x, y 是 G 的两个不同顶点，我们称 ( G, x, y ) 为有根图。有根图 ( G, x, y ) 的最小度为 min { d G ( v ) : v ∈ V ( G ) −{ x, y }} 。如果 G + xy 是2连通的，我们还称有根图 ( G, x, y ) 是2连通的。我们称 k 条路径或 k 条循环 P 1 , P 2 , . . . , P k 为
关于给定色数图中奇数圈的加强
主要关键词
相关文件推荐
