Structural graph theory front page

This means that it cannot be considered to contain or lead to any mathematically interesting information.

This article is incomplete. This article needs to be written; see below for some ideas.

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.

Login or register to post comments
5451 reads

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.