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 extremal-graph-theory
Search options not deleted
user 2233
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.
15
votes
Are all almost regular graphs obvious?
Here is an expansion of joro's answer.
Claim.
$K_{n, n+1}$ is obvious if and only if $n+1$ is even.
Proof. If $n+1$ is even, we can add a perfect matching on the vertices on the right to obtain a …
- 32.1k
12
votes
Accepted
Existence of triangle-free graphs for regular graphs of degree at most n/2
Yes, it is always possible to find regular triangle-free graphs of any degree up to half the number of vertices (as long as the number of vertices is even). To see this, by Hall's Theorem the edges o …
- 32.1k
11
votes
Accepted
The maximum number of edges in an even-cycle-free graph with $n$ vertices
The answer is $\lfloor \frac{3}{2}(n-1)\rfloor$. First note that if $G$ is $2$-connected and even-cycle-free, then $G$ must just be an odd cycle. To see this, consider an ear-decomposition of $G$. …
- 32.1k
8
votes
Reference request: monochromatic paths in edge-colored complete graphs
For $c=2$, it is a theorem of Gerencsér and Gyárfás that $P(k,2)=\lfloor (3k-2)/2 \rfloor$.
For $c=3$, Gyárfás, Ruszinkó, Sárközy and Szemerédi proved that for sufficiently large $k$,
$P(k,3)=2k-1 …
- 32.1k
6
votes
Is there a graph that is Ramsey for $P_{2n}$ but is $C_{2n+1}-$free
Taking $F=K_{4n, 4n}$ does the trick. To see this, suppose we have coloured each edge of $K_{4n,4n}$ red or blue. Let $R$ and $B$ be the red and blue subgraphs of $K_{4n,4n}$. We may assume that $R …
- 32.1k
6
votes
Accepted
Graph combinatorial optimization problem
The answer is $k=n-2$. To see this, first note that $k \geq n-2$, since the complete graph on $n$ vertices minus an edge has the desired property for $k=n-3$. For the other inequality suppose that $ …
- 32.1k
5
votes
How many simple cycles can a graph with $n$ vertices and $m$ edges have?
To supplement Igor's answer, here is some more information on the maximum number of cycles a graph on $n$ vertices with $m$ edges can have. I apologize that this does not answer your question. Entr …
- 32.1k
5
votes
Accepted
Density of bipartite $d$-degenerate graph
Theorem. A $d$-degenerate $n$-vertex bipartite graph has at most $\lceil \frac{n}{2} \rceil \lfloor \frac{n}{2} \rfloor$ edges if $n < 2d$ and at most $d(n-d)$ edges if $n \geq 2d$. Moreover, both …
- 32.1k
5
votes
Accepted
Sharp upper bound of the number of edges for graphs of thickness two
There is no such graph on $11$ vertices, but for all $n \geq 12$, there exists a thickness-$2$ graph with $6n-12$ edges. Both these results were proved by Boswell and Simpson in Edge-disjoint maximal …
- 32.1k
4
votes
Complete k-partite graph covers all K_k of a graph
For every graph $G$, the smallest number of complete bipartite subgraphs needed to cover the edges of $G$ is called the biclique covering number, and is denoted by $bc(G)$. The corresponding partitio …
- 32.1k
4
votes
Accepted
Size of forbidden minors for treewidth
Yes, an upperbound was proved in Upper Bounds on the Size of Obstructions and Intertwines by Lagergren. In case you cannot access the paper, the relevant theorem is Theorem 5.9.
If $G$ is an obstruc …
- 32.1k
3
votes
Minimal Non-planar Extensions of a Graph
For a connected example, take a path with 6 vertices. Then, $K_{3,3}$ and $K_5$ together with an additional edge sticking out are both minimal non-planar extensions, again obviously not isomorphic. …
- 32.1k
3
votes
What is the state of the art for the Turán number of $K_{4,4}$?
Here is a near answer. In Turan Numbers of Bipartite Graphs and Related Ramsey-Type Questions, Alon, Krivelevich, and Sudakov prove that $ex(n; K_{s,t}) \leq O(n^{2-1/s})$. They note that this bound …
- 32.1k
3
votes
Accepted
Extremal graph theory - many copies of $K_r$ imply a copy of $r$-chromatic $H$
This follows from Proposition 2.1 of the paper Many $T$ copies in $H$-free graphs by Alon and Shikhelman.
Theorem (Alon and Shikelman)
Let $T$ be a fixed graph with $t$ vertices. Then $ex(n,T,H)=\Ome …
- 32.1k
3
votes
Accepted
The lower bound of number of vertices covered by maximum matching in $3$-regular graph
The bound $\frac{7}{8}n$ is tight. The example shown below (image courtesy of David Eppstein) is a well-known cubic (planar) graph that has no perfect matching.
(source: uci.edu)
This graph has $16$ …
- 32.1k