Tricki
a repository of mathematical know-how

Graph decompositions

Graph decompositions

It would be nice if there were an article on using various graph decompositions. For example, it is very frequently useful to decompose a graph into one or more of the following:

  • connected components (or strongly connected components if dealing with directed graphs), though this is so frequently used it's almost trivial
  • 2-connected components
  • a tree decomposition (a la treewidth)
  • a clique decomposition (a la clique width)
  • some sort of product of other graphs (Cartesian product is particularly nice because it satisfies unique factorization)
  • others?

I am not experienced enough to write such an article, but thought I'd throw the idea out there.

[Already posted as a comment under the "Structural Graph Theory" stub, but reposted here as it seems appropriate.]