The tag has no wiki summary.

learn more… | top users | synonyms

19
votes
2answers
372 views

Is it necessary to call matrix multiplication $n$ times to find a claw

A claw is a $K_{1,3}$. A trivial algorithm will detect a claw in $O(n^4)$ time. It can be done in $O(n^{\omega+1})$, where $\omega$ is the exponent of fast matrix multiplication, as follows: take the ...
1
vote
2answers
255 views

Natural graph class with five excluded subgraphs?

I'm interested in hereditary graph classes characterized by a small number of excluded subgraphs. There are some well-known graph classes that are characterized by three or four obstructions -- ...
7
votes
1answer
219 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, ...
9
votes
2answers
297 views

Is there any triangle-free, star-cutset-free, circle graph, with more than n edges?

I'm trying to find a graph with those properties for my studies, but unfortunately I can't find such graph. Does anyone know if there is that graph, or why is it impossible to exist?
1
vote
0answers
101 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
324 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
219 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
648 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 ...
11
votes
1answer
246 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 ...
13
votes
3answers
673 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
443 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 ...
24
votes
4answers
743 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 ...