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.
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
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
2
votes
Clique number of $k$-critical graphs
For an upperbound, the clique number of a $k$-critical graph is obviously at most $k$, and this is achieved by the complete graph $K_k$. There is no non-trivial lowerbound for the clique number, and …
- 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
1
vote
Accepted
On the number of disjoint subsets of a large set families
Your first question is simply asking what is the minimum number of edges an $n$-vertex graph must have to force a matching of size $m$. This number was determined exactly by a classic result of Erdős …
- 32.1k
2
votes
Accepted
Is there any study on the bounds on the number of even cycles for planar bipartite graphs?
Every $n$-vertex planar graph has at most $O(n^k)$ copies of $C_{2k}$. Note that the bipartite assumption is not needed. A more general result is proven in my paper Subgraph densities in a surface w …
- 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
0
votes
Accepted
Maximum number of leaf blocks in 3-regular (cubic) graph
Yes, your conjecture is true. In fact, we can prove something stronger. All the extremal examples actually come from your construction. Say that a graph is special if it can be obtained from a $3$- …
- 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
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
2
votes
Number of edge-disjoint cycles in a holey graph
For a graph $G$, let $\nu(G)$ be the maximum number of edge-disjoint cycles, and let $\tau(G)$ be the minimum size of a set of edges $X$ such that $G-X$ has no cycles. Note that for a connected graph …
- 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
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
1
vote
Accepted
Lower bound on outdegree/indegree in oriented graph to guarantee cycle of length at least $k$
Out-degree $k-2$ is sufficient to force a directed cycle of length at least $k$. To see this, consider a longest directed path $P:=v_1v_2 \dots v_\ell$. Since $P$ is a longest path and there are no …
- 32.1k
2
votes
extremal bipartite graph
Edit. My previous upper bound was not correct. Thanks to Gilad for pointing that out.
If $m<k$, then of course it is not possible. Otherwise, for an upper bound start with a matching $M$ saturating …
- 32.1k