The graph-classes tag has no wiki summary.
0
votes
0answers
73 views
Edge Cut of interval graphs
On interval graphs, minimal vertex separators are well understood: they are cliques, there are no more than $n$ ones. However, when we turn to the minimal edge cut, my search found no even one single ...
11
votes
1answer
299 views
Does this graph class have a name ?
It's formulated by extending threshold graphs. Given a threshold graph $(C,I)$ where $C$ is the clique and $I$ is the independent set, my extension is as follows: Each vertex $v\in I$ can be replaced ...
5
votes
2answers
208 views
Is any chordal graph an incomparability graph?
I was confused by Wikipedia's definitions of "chordal graph", "interval graph", "string graph", "comparability graph", "incomparability graph" and the complements of these.
Wikipedia says "The ...
5
votes
4answers
502 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 ...
10
votes
1answer
218 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 ...
11
votes
3answers
555 views
Classes of graphs with easy Hamiltonian cycle but NP-hard TSP
The Hamiltonian Cycle Problem (HC) consists in finding a cycle that goes through all vertices in a given undirected graph. The Travelling Salesman Problem (TSP) consists in finding a cycle that goes ...
15
votes
1answer
394 views
Reference for (odd-hole,antihole)-free graphs?
X-free graphs are those that contain no graph from X as an induced subgraph. A hole is a cycle with at least 4 vertices. An odd-hole is a hole with an odd number of vertices. An antihole is the ...
18
votes
3answers
545 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 ...
