Skip to main content
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
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.

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 …
Vinicius dos Santos's user avatar
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 …
Vinicius dos Santos's user avatar
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 …
Vinicius dos Santos's user avatar
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 …
Vinicius dos Santos's user avatar
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 …
Vinicius dos Santos's user avatar
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 …
Vinicius dos Santos's user avatar
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 …
Vinicius dos Santos's user avatar
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 …
Vinicius dos Santos's user avatar
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 …
Vinicius dos Santos's user avatar