Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with co.combinatorics
Search options not deleted
user 8193
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
3
votes
Upper-bound for maximal-cliques on perfect graphs
Cographs form a subclass of perfect graphs and there are examples of cographs with an exponential number of cliques. For example, consider the complement of a perfect matching on $n$ vertices. It is e …
0
votes
Are there any non-planar graphs containing only K(3,3) as a subgraph that are not 4-colourable?
If you are looking for a non 4-colorable graph free of a $K_5$ as subgraph, the simpler way would be taking a non 4-colorable graph and adding a disjoint copy of $K_{3,3}$. One such graph is the Mycie …
1
vote
Tree decomposition of graphs with low height
One way to address this question is to think of a tree decomposition as an unrooted tree. Then, it is easy to see that its diameter is related to the depth by a factor of 2. Searching for diameter, in …
1
vote
Partitioning the vertex set of a planar bipartite graph into a tree and an independent set
I don't know the answer for your question, but I know a somewhat related problem.
In this paper it is shown that, given a planar bipartite cubic graph $G$ and a set $W$ of vertices, it is NP-complete …
2
votes
1
answer
681
views
Maximum number of hyperedges on a hypergraph without a spanning tree
Although every connected graph has a spanning tree, the same is not true for hypergraphs: consider the hypergraph on 4 vertices with all possible edges of size 3. You need to pick at least two edges b …
8
votes
Making a graph claw-free by adding as few edges as possible
I don't know whether it is possible to find a small set of edges to add in order to make a graph claw-free efficiently, but I think this is not a good approach for approximating MIS.
Consider the sta …
2
votes
Automatically generating combinatorial conjectures
Not sure whether this is exactly what you are looking for or whether you may consider this solution kind of cheating, but you may be interested in the Berlekamp–Massey algorithm, that can be used to f …
3
votes
Accepted
Real-world datasets for testing the maximum edge bi-clique problem
Since this problem has many applications in data mining, you probably should take a look at datasets used as benchmarks in papers on the topic. As an example, this recent paper mostly uses graphs from …
2
votes
Can we say a partial order set is 2-dimensional if its comparability graph does not contain ...
It seems that the answer is negative.
A graph $G$ is a co-comparability graph if its complement is a comparability graph. The comparability graphs of posets of dimension 2 are exactly the comparabilit …