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


Yes, Matiyasevich uses his method of proving statements, introduced in that paper, to prove theorem stated as "Graph \( L \) can be \( n \)-colored iff all edges of \( L \) can be oriented such that resulted oriented graph has no path of length \( n \)".