One main aim of my work on local-global decompositions is to define a graph width parameter which captures precisely when a graph has dense local structure. Width in this context is the maximum size of a bag of a certain kind of graph-decomposition. So, for notions of “local width” to succeed, bags of decompositions must interact in some way with local dense structures. But how, exactly?
In a previous post, I discussed some reasons why I like the definition of graph-decomposition. But why do I care about graph-decompositions to begin with? In this post, I go deeper into what I hope graph-decompositions can do.
An explanation of our unusual definition of local.
A list of papers I want to read in the near future.
Graph-decompositions are defined by taking the definition of tree-decomposition, crossing out “tree”, and writing “graph” instead. Is this the right definition?
The local cover is a new object designed to model the local structure of a graph. I wrote a survey explaining the local cover.
My paper on locally chordal graphs appeared on arXiv! (See also: a recent talk I gave about this topic.) I’m very happy about this paper! In this post, I try to explain why.