Questions tagged [graph-classes]
The graph-classes tag has no usage guidance.
4
questions
32
votes
5
answers
1k
views
Maximal classes for which largest independent set can be found in polynomial time?
The ISGCI lists over 1100 classes of graphs. For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called IS-easy classes. I would like to compile ...
- 19k
12
votes
1
answer
419
views
Do "outer-bounded-genus" graphs have constant treewidth?
Let $k\in\mathbb{N}$ and denote by $G_k$ the set of all graphs that can be embedded on a surface of genus $k$ such that all vertices are situated on the outer face. For instance, $G_0$ is the set of ...
- 817
8
votes
1
answer
329
views
Can a natural graph problem be universally hard?
Is there a natural $\mathsf{NP}$-complete graph problem, which remains $\mathsf{NP}$-complete even when it is restricted to any polynomial-time recognizable graph class? To avoid degenerated cases, ...
- 11.4k
5
votes
4
answers
901
views
Hard problems on subclasses of planar cubic bipartite graphs
Several hard graph problems remain hard on planar cubic bipartite graphs. They include Hamiltonian cycle problem and perfect P3 matching problem. I'm looking for a reference on interesting subclasses ...
- 20.9k