More graph theory

I've been slowly working my way through a copy of Sparsity: Graphs, Structures, and Algorithms, by Nešetřil and Ossona de Mendez, and as I do finding topics whose coverage in Wikipedia could use improvement:

• Tree-depth (split off from a related existing article on cycle rank), the minimum clique size of a trivially perfect supergraph of the given graph. This has the nice properties that

  1. on sparse families of graphs, bounded tree-depth is equivalent to the nonexistence of a long induced path, and

  2. on graphs of bounded tree-depth, any hereditary graph property has a finite set of forbidden induced subgraphs.

  Based on these properties, it's easy to extend the recognition algorithm for 1-planar threshold graphs that I recently posted about to also recognize 1-planar cographs and split graphs: first make sure the graph is sparse enough to be 1-planar, and if so use dynamic programming on a tree-decomposition derived from the DFS tree to test for the existence of the forbidden subgraphs.

• Bramble, a generalization of a clique minor used to characterize treewidth.

• Gallai–Hasse–Roy–Vitaver theorem, the theorem that the chromatic number of a graph is the same as the minimum, over all orientations of the graph, of the longest path length in the orientation. This is what I was using (without knowing it) in my SODA '10 paper showing that it's possible to find either a long path or a good coloring in any undirected graph, even though both the longest path and coloring problems are very hard to approximate. Along the way I was also led to create new articles on orientations and acyclic orientations.

[Incidentally, if anyone who can read Russian sees this: I suspect this paper (MR363823) by Matiyasevich may be about the same theorem, but I can't read it to tell for sure. So I'd appreciate any clarification anyone might have.]

Comments: