The extremal-graph-theory tag has no wiki summary.

**5**

votes

**3**answers

714 views

### Online Library of Unlabeled Connected Graphs on n Vertices

Does anyone know of the link to an online library of of unlabeled, connected graphs on n vertices? I remember looking at such an archive a few years ago while at a Macaulay 2 workshop, but I've been ...

**6**

votes

**0**answers

333 views

### Cliques of hyperedges

Suppose we have a graph, with multiple edges allowed. An edge-clique is a set $C$ of edges so that every two edges in $C$ share at least one endpoint. Note that any edge-clique falls into one of two ...

**1**

vote

**2**answers

467 views

### Bounds on the independence number of a graph

If $G$ is a graph with $n$ vertices and $\frac{nk}{2}$ edges, $k\ge -1,$ then $a(G)\ge \frac{n}{k+1}$. Why?
(Here $a(G)$ is the independence number).

**6**

votes

**2**answers

456 views

### Is the feedback vertex number bounded by the maximum number of leaves in a spanning tree?

I have a graph-theoretical conjecture which I think would have been studied before, but for which I cannot find anything in the literature.
Let G be a finite, simple, connected graph. Let the ...

**2**

votes

**1**answer

376 views

### Suppose the independent number of a graph is bounded. How small the clique number can be?

Suppose the independent number of a graph is bounded. How small the clique number can be? linear?
It seems to be a natural problem to ask. but I could not find any reference.
Thanks.

**1**

vote

**2**answers

409 views

### Minimal Non-planar Extensions of a Graph

Given a planar graph $G=(V,E)$ with vertices $V$ and edges $E$, call $\bar G = (V,\bar E)$ a non-planar extension of $G$ if $\bar G$ is non-planar and $E \subset \bar E$.
I'm interested in minimal ...

**4**

votes

**3**answers

784 views

### Erdős–Stone theorem type edge density estimates for bipartite graphs?

The Erdős–Stone theorem theory says that the densest graph not containing a graph H (which has chromatic number r) has number of edges equal to $(r-2)/(r-1) {n \choose 2}$ asymptotically.
However, ...