# Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

581 questions
888 views

670 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 ...
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 ...
611 views

### Non-hamiltonian Graphs with unique hamiltonian path between exactly 4 pair of vertices

Need some example graphs which are not Hamiltonian, i.e, does not admit any Hamiltonian cycle, but which have Hamiltonian path. It has Hamiltonian paths between exactly 4 pair of vertices. I have ...
666 views

### Are there local maxima in the number of moves required to solve a Rubik's Cube?

Peter Shor brought up an interesting point in relation to an attempt to answer an earlier question on the complexity of solving the $n \times n \times n$ Rubiks cube. I had posted a rather naive ...
1k views

216 views

### How can one construct a densest graph with no k-clique?

Given integers $k$ and $n$ with $2 \le k < n$, how does one construct a graph on $n$ vertices that contains no $k$-clique and has the maximal number of edges? This sounds like basic ...
1k views

### Properties of Random Directed Graphs with Fixed Out-Degree

I am interested in properties of random directed graphs with fixed out-degree $d$. I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r. ...
937 views

### Graph Theory Fun Problem

Show that in any graph $G$ with min-degree $k$ ($k \geq 1$ duh!) you can find as its subgraph any tree on $k+1$ vertices. I have not been able to solve the question so far. However, I would like if ...
505 views

341 views

### Finding small sets of integers in which every element is a sum of two others

This is a follow-up to this question on math.stackexchange. Let us say that a non-empty set S ⊆ ℤ is self-supporting if for every a ∈ S, there exist distinct ...
341 views

### Cliquewidth of Almost Cographs

(I posted this question to MathOverflow two weeks ago, but so far without a rigorous answer) I have a question about graph width measures of undirected simple graphs. It is well-known that cographs (...