All Questions
Tagged with lower-bounds graph-theory
8 questions
1
vote
1
answer
365
views
Tree width and clique width of regular graphs
Consider a $k$ regular graph of $n$ vertices, where $3 \leq k \leq (n-1)$. Is there any upper or lower bound, in the worst case, known for either the tree-width or the clique width of each $k$ regular ...
2
votes
1
answer
96
views
Lower bound on the number of balanced graphs
Let $\alpha>1$ be a constant and define $B_n$ as the number of (labeled) balanced graphs with $n$ vertices and $\left\lceil \alpha n\right\rceil $ edges. The paper Strongly Balanced Graphs
and ...
- 143
7
votes
1
answer
310
views
Is this lower bound for the size of minimal vertex cover new/interesting?
I have found this lower bound for the size of minimal vertex cover (and proved it).
If a simple connected graph G on n vertices has largest and smallest eigenvalues $\lambda_1,\lambda_n$, ...
- 133
1
vote
0
answers
113
views
Bounds on spectral radius using chromatic number
I am struggling with this question:
If I have a connected graph $G$ on $n$ vertices and $m$ edges with chromatic number $d$ then how can I give a bound(lower and upper) on its spectral radius in ...
- 135
3
votes
0
answers
212
views
Lower bound on number of $r$-regular graphs witn $n$ vertices
Consider the set of $r$-regular labeled graphs with $n$ vertices. There are results on its asymptotic size (see for instance this question on MO).
Is there a known, explicit lower bound on that size, ...
- 81
3
votes
1
answer
575
views
Minimum number of perfect matchings in a regular bipartite graph
Is there a lower bound on the number of perfect matchings in a $k$-regular bipartite graph?
One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up ...
- 217
1
vote
3
answers
238
views
Minimum number of unlabeled planar graphs
Does anybody know if there is any research on a lower bound on the number of (non-isomorphic) unlabeled planar graphs with maximum node degree $d$?
Alternatively, a lower bound on the number of all ...
- 11
17
votes
6
answers
10k
views
Lower bounds for chromatic number of a graph
I am trying to find a good lower bound for chromatic number of one family of graphs. I'm curious what are the known lower bounds for chromatic number. There are two obvious: $\chi(G) \geq \omega(G)$ ...
- 1,791