# Questions tagged [extremal-graph-theory]

Study of graphs satisfying a property that are maximal or minimal with respect to some parameter. A classic example is Turán's Theorem, which exactly characterizes the densest graphs on $n$ vertices without a $K_t$ subgraph.

186 questions
Filter by
Sorted by
Tagged with
1 vote
65 views

### Partitioning of a set family that avoids small intersections

Let $\mathcal{F}$ be the family of all $k$-element subsets of $[n]$. What is the smallest $\ell$ such that we can partition $\mathcal{F}$ into $\ell$ families $F_1,\dots,F_\ell$ with the property that ...
76 views

17 views

424 views

### Graph that minimizes the number of b/w colorings where white vertices have an odd number of black

motivated from a physical context, we are currently interested in the following graph coloring problem: Given a connected graph $G_n$ with $n$ vertices, how many colorings exist such that all white ...
85 views

### Smallest size of graph covered by infinite tree

Let $T$ be the universal covering tree of some finite, connected, non-tree graph, and let $n_0(T)$ be the smallest positive integer such that there exists a graph $G$ (loops and multiple edges allowed)...
77 views

### Making graphs isomorphic with edge additions/removals

Consider simple graphs on the same vertex set $[n]$. For two graphs $G, H$, let $d(G, H) = \min_{H' \sim H} |E(G) \triangle E(H')|$ — the smallest number of edge additions/removals needed to make $G$ ...
536 views

### Spanning trees: the last darn $1/4$

Let $\Gamma$ be a connected graph. By (Kleitman-West, 1991), if every vertex of $\Gamma$ has degree $\geq 3$, then $\Gamma$ has a spanning tree with $\geq n/4+2$ leaves, where $n$ is the number of ...
153 views

### Szemerédi's regularity lemma for binary operations

Szemerédi's regularity lemma is an approximate structure theorem for all large graphs (symmetric binary relations). There are versions for multicolored graphs and directed graphs. Is there an ...
121 views

### Largest number of simple paths between two vertices

Let $G$ be a simple undirected graph, $f(v, u)$ be the number of simple paths between $u$ and $v$ in $G$, $f(G) = \max f(v, u)$ over all pairs of vertices $v, u \in G$. A recent IOI problem utilized ...
119 views

It's well known that a $C_4$-free graph of order $n$ has average degree $O(\sqrt{n})$, and it follows that the independence number is $\Omega(\sqrt{n})$. This bound cannot be improved over $\Theta(n^{\... 3 votes 0 answers 75 views ### Connected set of vertices having large boundary in a subset? Let$\Gamma = (V,E)$be a connected (undirected) graph where every vertex has degree$\geq 2$. Let$E'\supset E$be a larger set of edges between elements of$V$such that every vertex of$\Gamma'=(V,...
Let $\Gamma, \Xi$ be two graphs with the same set of vertices $V$ with $n$ elements. Assume $\Gamma$ is connected. Write $\Gamma\cup \Xi$ (or $\Gamma\cap \Xi$) for the graph whose set of edges is the ...