TR-2007-05

Brick Partitions of Graphs

Bill Jackson, Tibor Jordán

Published in:
Discrete Mathematics, Vol. 310, no. 2, 2010, pp. 270-275.

For each rational number q \geq 1, we describe two partitions of the vertex set of a graph G, called the q-brick partition and the q-superbrick partition. The special cases when q=1 are the partitions given by the connected components and the 2-edge-connected components of G, respectively. We obtain structural results on these partitions and describe their relationship to the principal partitions of a matroid.

Bibtex entry:

@techreport{egres-07-05,

AUTHOR	=	{Jackson, Bill and Jord{\'a}n, Tibor},
TITLE	=	{Brick Partitions of Graphs},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2007},
NUMBER	=	{TR-2007-05}

}