Name
Title | ||
|---|---|---|
A lower bound on the independence number of a graph in terms of degrees and local clique sizes |
Abstract | ||
|---|---|---|
Caro and Wei independently showed that the independence number (G) of a graph G is at least uV(G)1dG(u)+1. In the present paper we conjecture the stronger bound (G)uV(G)2dG(u)+G(u)+1 where G(u) is the maximum order of a clique of G that contains the vertex u. We discuss the relation of our conjecture to recent conjectures and results concerning the independence number and the chromatic number. Furthermore, we prove our conjecture for perfect graphs and for graphs of maximum degree at most 4. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.dam.2015.06.009 | Discrete Applied Mathematics |
Keywords | Field | DocType |
degree,independent set,clique | Perfect graph,Discrete mathematics,Combinatorics,Clique,Bound graph,Vertex (geometry),Upper and lower bounds,Independent set,Degree (graph theory),Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
209 | C | 0166-218X |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| christoph brause | 1 | 18 | 7.30 |
| Bert Randerath | 2 | 243 | 25.79 |
| Dieter Rautenbach | 3 | 946 | 138.87 |
| Ingo Schiermeyer | 4 | 667 | 89.41 |