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
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,403
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
1 vote

Maximal classes for which largest independent set can be found in polynomial time?

In the meantime, it was shown that the problem is polynomial-time solvable on $P_6$-free graphs: Andrzej Grzesik, Tereza Klimosov√°, Marcin Pilipczuk, Michal Pilipczuk: Polynomial-time Algorithm for ...
Christian Komusiewicz's user avatar

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