Questions tagged [graph-classes]
The graph-classes tag has no usage guidance.
22 questions
1
vote
0
answers
84
views
Is there any augmenting graph algorithm available for finding maximum independent set problem in K1,4-free graph in polynomial time
$K_{1,4}$-free graph is the graph with no induced subgraph of the form $K_{1,4}$
An augmenting graph $H$ for $S$ (which is an independent set) is an induced bipartite subgraph of $G$, where $H = (B, ...
- 27
0
votes
0
answers
73
views
Is every 4-claw-free graph a bounded degree graph?
I am looking of some graph properties of 4-claw free graph, where neighborhood of every vertex has independent set of size at most 3.
As per my observations, this type of independent set size ...
- 27
1
vote
1
answer
70
views
Treewidth of monotone graph classes with bounded cliquewidth
Assume a graph class excludes a certain bicique $K_{n,n}$ and has bounded cliquewidth. Then by a result of Gurski and Wanke, this class also has bounded treewidth.
Is there a similar result that ...
- 61
-1
votes
1
answer
144
views
What are the known classes of undirected graphs such that every graph belonging to that class is guaranteed to have a Hamiltonian Path?
One trivial class of graphs is the class consisting of complete graphs or complete bipartite graphs with equal sized partitions.
I would love to know if more such classes exist.
- 137
7
votes
1
answer
126
views
Extending cographs with product operation
Let $\mathcal{C}$ be the class of undirected graphs defined inductively as follows:
A single vertex is in $\mathcal{C}$;
If $G\in\mathcal{C}$ then its complement $\overline{G}$ is in $\mathcal{C}$;
...
- 161
9
votes
0
answers
109
views
Forbidden Subgraph Characterization for Graphs with few Maximal Cliques
Consider the following property of undirected graphs. A graph has the $s$-vertex overlap property if every vertex is contained in at most $s$ maximal cliques. I am interested in forbidden induced ...
- 2,039
5
votes
0
answers
118
views
Open Problems About Nowhere-Dense Classes of Graphs
I'm writing a survey about nowhere-dense graphs. I would like to list some of the main open problems in the field. In particular I would like to list problems of the following form.
The problem has ...
- 696
1
vote
1
answer
192
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 P_5-...
- 1,955
11
votes
2
answers
428
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 ...
- 620
4
votes
2
answers
388
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.
...
- 1,955
21
votes
2
answers
526
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 ...
- 2,569
2
votes
3
answers
338
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 -- ...
- 29
8
votes
1
answer
330
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
9
votes
2
answers
405
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
0
answers
213
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 ...
- 2,569
13
votes
1
answer
447
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 ...
- 2,569
6
votes
2
answers
347
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 ...
- 1,463
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 ...
- 21.1k
12
votes
1
answer
422
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 ...
- 837
14
votes
3
answers
1k
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 ...
- 965
16
votes
1
answer
959
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 ...
- 19.2k
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 ...
- 19.2k