Tricki
a repository of mathematical know-how

Structural graph theory front page

Stub iconThis article is a stub.This means that it cannot be considered to contain or lead to any mathematically interesting information.
Note iconIncomplete 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.

Comments

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)
- 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.