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
3 votes

What are the known classes of undirected graphs such that every graph belonging to that class is guaranteed to have a Hamiltonian Path?

A good resource to answer questions like this is graphclasses.org. You find the graph class you care about -- in this case, Hamiltonian graphs. Then check the maximal subclasses section, and ...
GMB's user avatar
  • 2,393
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
2 votes

Natural graph class with five excluded subgraphs?

Graphs where every connected component is a split graph are (C4, C5, P5, necktie, bowtie)-free (see A graph modification approach for finding core–periphery structures in protein interaction networks)....
Falk Hüffner's user avatar

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