![]() |
![]() |
Quick description
This page concerns a distinctive subarea of combinatorics, with its own set of methods, that includes famous results such as the four-colour theorem, the Robertson-Seymour theorem and the strong perfect graph theorem. Insight into how one goes about proving this kind of result would be very welcome.
Comments
Graph decompositions
Thu, 09/04/2009 - 05:06 — Josh (not verified)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)
- 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.