Partitioning into graphs with only small components

被引：66

作者：

Alon, N ^{[1
]}

Ding, GL

Oporowski, B

Vertigan, D

机构：

[1] Tel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel

[2] Louisiana State Univ, Dept Math, Baton Rouge, LA 70803 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2003年 / 87卷 / 02期

关键词：

tree-width; vertex partitions; edge partitions; small components;

D O I：

10.1016/S0095-8956(02)00006-0

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The paper presents several results on edge partitions and vertex partitions of graphs into graphs with bounded size components. We show that every graph of bounded tree-width and bounded maximum degree admits such partitions. We also show that an arbitrary graph of maximum degree four has a vertex partition into two graphs, each of which has components on at most 57 vertices. Some generalizations of the last result are also discussed. (C) 2002 Elsevier Science (USA). All rights reserved.

引用

页码：231 / 243

页数：13

共 12 条

[1] THE LINEAR ARBORICITY OF GRAPHS [J].

ALON, N .

ISRAEL JOURNAL OF MATHEMATICS, 1988, 62 (03) :311-325

[2] Linear arboricity and linear k-arboricity of regular graphs [J].

Alon, N ;

Teague, VJ ;

Wormald, NC .

GRAPHS AND COMBINATORICS, 2001, 17 (01) :11-16

[3]

ALON N, 1992, PROBABILISTIC METHOD

[4]

[Anonymous], 1891, Acta Mathematica, DOI DOI 10.1007/BF02392606

[5]

DEVOS M, EXCLUDING ANY GRAPH

[6]

DING G, PARTITIONING GRAPHS

[7] On tree-partitions of graphs [J].

Ding, GL ;

Oporowski, B .

DISCRETE MATHEMATICS, 1996, 149 (1-3) :45-58

[8]

Erdos P., 1963, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, V12, P251

[9]

HAXELL P, NOTE VERTEX LIST COL

[10] ON THE BANDWIDTH OF TRIANGULATED TRIANGLES [J].

HOCHBERG, R ;

MCDIARMID, C ;

SAKS, M .

DISCRETE MATHEMATICS, 1995, 138 (1-3) :261-265

← 1 2 →