Vertex partitions of K4,4-minor free graphs

被引:11
作者
Jorgensen, LK [1 ]
机构
[1] Univ Aalborg, Dept Math, DK-9220 Aalborg O, Denmark
关键词
D O I
10.1007/PL00007245
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We prove that a 4-connected K-4,K-4-minor free graph on n vertices has at most 4n-8 edges and we use this result to show that every K-4,K-4-minor free graph has vertex-arboricity at most 4. This improves the case (n, m) = (7, 3) of the following conjecture of Woodall: the vertex set of a graph without a K-n-minor and without a K-[n+1/2],K-[n+1/2]-minor can be partitioned in n - m + 1 subgraphs without a K-m-minor and without a K-[m+1/2],K-[m+1/2]-minor.
引用
收藏
页码:265 / 274
页数:10
相关论文
共 13 条
  • [1] EVERY PLANAR MAP IS 4 COLORABLE .1. DISCHARGING
    APPEL, K
    HAKEN, W
    [J]. ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) : 429 - 490
  • [2] EVERY PLANAR MAP IS 4 COLORABLE .2. REDUCIBILITY
    APPEL, K
    HAKEN, W
    KOCH, J
    [J]. ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) : 491 - 567
  • [3] POINT-ARBORICITY OF PLANAR GRAPHS
    CHARTRAND, G
    KRONK, HV
    [J]. JOURNAL OF THE LONDON MATHEMATICAL SOCIETY, 1969, 44 (176P): : 612 - +
  • [4] CHARTRAND G, 1971, J COMB THEORY B, V10, P12
  • [5] Surfaces, tree-width, clique-minors, and partitions
    Ding, GL
    Oporowski, B
    Sanders, DP
    Vertigan, D
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2000, 79 (02) : 221 - 246
  • [6] HADWIGER HUGO, 1943, Vierteljahrsschr Naturforsch Ges Zurich, V88, P133
  • [7] HANSON D, 1994, B I COMBIN APPL, V11, P59
  • [8] Jacob H., 1983, ANN DISCRETE MATH, V17, P365
  • [9] CONTRACTIONS TO K8
    JORGENSEN, LK
    [J]. JOURNAL OF GRAPH THEORY, 1994, 18 (05) : 431 - 448
  • [10] KRONK HV, 1974, J LOND MATH SOC, V9, P459