The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
162 views

Two paper appear to imply collapse via coloring $P_5$-free graphs

Found this from graphclasses.org. Two papers give conflicting results for coloring $P_5$-free graphs which appear to imply $P=NP$. From Polynomial-time algorithm for vertex k-colorability of ...
10
votes
2answers
212 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
341 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
413 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
248 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
309 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
352 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
743 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
272 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
754 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
481 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
857 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 ...