The tag has no wiki summary.

learn more… | top users | synonyms

10
votes
2answers
207 views

Name the graph class: Disjoint union of a clique and an independent set

Let $G$ be a graph which is the disjoint union of a clique and an independent set, i.e. $$G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} .$$ The graph class of all such graphs is characterized ...
4
votes
2answers
339 views

Weird claim of graphclasses about complexity of domination

EDIT this got 'fixed' on graphclasses, as per answers/comments, so you might not reproduce it, unless you have their earlier database, which is publicly available via sage - http://sagemath.org. ...
20
votes
2answers
411 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
263 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 -- ...
8
votes
1answer
244 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
307 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
110 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 ...
12
votes
1answer
349 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
230 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
740 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
271 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
752 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 ...
16
votes
1answer
478 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
854 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 ...