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.
253 questions
-1
votes
1
answer
94
views
Existence of a graph with strong restrictions
Given a maximal degree $k$ and maximal diameter $d$. We identify 3 nodes, $i$, $j$, and $v$. Can an undirected graph exist, such that:
all nodes but $v$ have full degree $k$ ($v$ having a lower ...
-1
votes
1
answer
199
views
Maximum degree and matching number
Let $G=(V,E)$ be a finite graph. We write $\nu(G)$ for the matching number of $G$. Is there $\varepsilon > 0$ such that we have $$\frac{\nu(G)+\Delta(G)}{V(G)} \geq \varepsilon$$ for all finite ...
- 48.9k
-3
votes
2
answers
349
views
Concepts of criticality in graph theory
A graph $G=(V,E)$ is said to be vertex-critical if removing a vertex $v\in V$ reduces the chromatic number $\chi(\cdot)$. Edge-criticality is defined in a similar manner. Moreover, $G$ is called ...
- 48.9k