Vertex Partitions of Chordal Graphs

Details Vertex Partitions of Chordal Graphs Vertex Partitions of Chordal Graphs

2004-08-07

arxiv.org/abs/math/0408098v1

J. Graph Theory, 53:167-172, 2006.

Mathematics

Combinatorics

submitted to a journal

Scientific paper

A \emph{$k$-tree} is a chordal graph with no $(k+2)$-clique. An \emph{$\ell$-tree-partition} of a graph $G$ is a vertex partition of $G$ into `bags', such that contracting each bag to a single vertex gives an $\ell$-tree (after deleting loops and replacing parallel edges by a single edge). We prove that for all $k\geq\ell\geq0$, every $k$-tree has an $\ell$-tree-partition in which every bag induces a connected $\floor{k/(\ell+1)}$-tree. An analogous result is proved for oriented $k$-trees.

Affiliated with

Also associated with

No associations

Rating

Vertex Partitions of Chordal Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Vertex Partitions of Chordal Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vertex Partitions of Chordal Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-274684