Partition and coloring of a graph

A3-至少不能在最少t和最多2 t-1被划分为连接的子图。使用此结果，我们可以显示一个3-连接的订单图，其中最少包含一个连接的订单子图，每个订单的数目和最多为8 - 1。对于一本3页书嵌入一个顺序n和大小m的图表，边缘交叉的最小数量的顺序或脊柱是O （m log d1 n D1）。让G是一个k-连接的顺序图p， p-n是甚至， α是一个与D 71（/）2 D 7 ≤ α ≤ 1和支持的真实数字|A（a）|>α（p-2k + n-2）+k为任何特定子集A的G| A（A）|=[α（k-n+2）]然后G是n因素关键的。Let G be a balanced bipartite graph of order 2 n、K__ Suppose_D21_然后是任何独立的边缘。EイイD21イイD2，-

・A 3-connected graph of order at least t can be partitioned into connected subgraphs of order at least t and at most 2t-1. Using this result, we can show that a 3-connected graph of order at least t contains a connected subgraph of order t whose degree sum is at most 8t-1.・For a 3-page book embedding of a graph of order n and size m, the order of the minimum number of edge-crossings orer the spine is O (m logィイD1nィエD1).・Let G be a k-connected graph of order p, p-n is even, α is a real number with ィイD71(/)2ィエD7≦α≦1, and suppose |Na(a)|>α(p-2k+n-2)+k for any indegredant subset A of G with |A|=[α(k-n+2)]. Then G is n-factor-critical.・Let G be a balanced bipartite graph of order 2n, K≧2, n≧2k.. Suppose σィイD21ィエD2,(G1)≧ max {n+k, [ィイD72n-1(/)3ィエD7]+2k} or δ(G)≧ max {[ィイD7n+k(/)2ィエD7],[ィイD72n+4k(/)5ィエD7]}. Then for any independent edges. EィイD21ィエD2,---, eィイD2kィエD2, G can be partitioned into disjoint cycles CィイD21ィエD2,----, CィイD2kィエD2 satisfying eィイD2iィエD2 εE (GィイD2iィエD2) 1≦I≦k..