Surfaces, tree-width, clique-minors, and partitions

被引：27
作者：
Ding, GL [1 ]
Oporowski, B [1 ]
Sanders, DP [1 ]
Vertigan, D [1 ]
机构：
[1] Louisiana State Univ, Dept Math, Baton Rouge, LA 70803 USA
来源：
JOURNAL OF COMBINATORIAL THEORY SERIES B | 2000年 / 79卷 / 02期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1006/jctb.2000.1962
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In 1971. Chartland. Geller, and Hedetniemi conjectured that the edge set of a planar graph may be partitioned into two subsets, each of which induces an outerplanar graph. Some partial results towards this conjecture are presented. One such result, in which a planar graph may be thus edge partitioned into two series-parallel graphs. has nice generalizations for graphs embedded onto an arbitrary surface and graphs with no large clique-minor. Several open questions are raised. (C) 2000 Academic Press.
引用
收藏
页码：221 / 246
页数：26
相关论文
共 38 条
  • [1] Appel Kenneth., 1989, CONTEMP MATH-SINGAP, V98
  • [2] FORBIDDEN MINORS CHARACTERIZATION OF PARTIAL 3-TREES
    ARNBORG, S
    PROSKUROWSKI, A
    CORNEIL, DG
    [J]. DISCRETE MATHEMATICS, 1990, 80 (01) : 1 - 19
  • [3] CHARACTERIZATION AND RECOGNITION OF PARTIAL 3-TREES
    ARNBORG, S
    PROSKUROWSKI, A
    [J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (02): : 305 - 314
  • [4] ARNBORG S, 1985, BIT, V25, P2, DOI 10.1007/BF01934985
  • [5] ACYCLIC COLORINGS OF PLANAR GRAPHS
    BORODIN, OV
    [J]. DISCRETE MATHEMATICS, 1979, 25 (03) : 211 - 236
  • [6] POINT-ARBORICITY OF A GRAPH
    CHARTRAND, G
    KRONK, HV
    WALL, CE
    [J]. ISRAEL JOURNAL OF MATHEMATICS, 1968, 6 (02) : 169 - +
  • [7] POINT-ARBORICITY OF PLANAR GRAPHS
    CHARTRAND, G
    KRONK, HV
    [J]. JOURNAL OF THE LONDON MATHEMATICAL SOCIETY, 1969, 44 (176P): : 612 - +
  • [8] CHARTRAND G, 1971, J COMB THEORY B, V10, P12
  • [9] COLBOURN CJ, 1988, C NUMER, V66, P69
  • [10] DING G, EXCLUDING ANY GRAPH
1234