Skip to main content
5 votes

Extending cographs with product operation

A path has cliquewidth $3$, but the tensor product of two paths of length $n$ will contain a $\Omega(n) \times \Omega(n)$ size grid as an induced subgraph. And $n \times n$ grids are known to have ...
daniello's user avatar
  • 3,266
4 votes

Is there a standard axiomatization of graph width parameters?

This isn't quite what you were asking for, but one of the first papers on treewidth found this parameter by axiomatizing a lattice of parameters for graphs, among which treewidth is the top element. ...
David Eppstein's user avatar
2 votes

Treewidth of monotone graph classes with bounded cliquewidth

Yes, the statement is true. Take a monotone class with bounded cliquewidth. We show that the size of bicliques is bounded. If it were not bounded, we could remove some edges and vertices (by ...
Jan's user avatar
  • 61

Only top scored, non community-wiki answers of a minimum length are eligible