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.

Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)

snapshot
Notifications