Skip to main content
Top

2002 | OriginalPaper | Chapter

The Structural Decomposition

Authors : Michael Molloy, Bruce Reed

Published in: Graph Colouring and the Probabilistic Method

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

In this chapter we will obtain a decomposition theorem for general graphs similar to that obtained in Chap. 11 for minimal counterexamples to the Beutelspacher-Hering Conjecture. That is, we will partition V (G) into sets D1,..., D ι and S where the D i are “dense clique-like” sets and all the vertices in S are sparse.

Metadata
Title
The Structural Decomposition
Authors
Michael Molloy
Bruce Reed
Copyright Year
2002
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-04016-0_15