Abstract | ||
---|---|---|
The independence number α ( H ) of a hypergraph H is the maximum cardinality of a set of vertices of H that does not contain an edge of H . Generalizing Shearer's classical lower bound on the independence number of triangle-free graphs Shearer (1991), and considerably improving recent results of Li and Zang (2006) and Chishti et¿al. (2014), we show that α ( H ) ¿ ¿ u ¿ V ( H ) f r ( d H ( u ) ) for an r -uniform linear triangle-free hypergraph H with r ¿ 2 , where f r ( 0 ) = 1 , and f r ( d ) = 1 + ( ( r - 1 ) d 2 - d ) f r ( d - 1 ) 1 + ( r - 1 ) d 2 for¿ d ¿ 1 . |
Year | DOI | Venue |
---|---|---|
2016 | 10.1016/j.disc.2016.01.006 | Discrete Mathematics |
Keywords | Field | DocType |
Independence,Hypergraph,Linear,Uniform,Double linear,Triangle-free | Discrete mathematics,Graph,Independence number,Combinatorics,Vertex (geometry),Generalization,Upper and lower bounds,Constraint graph,Hypergraph,Cardinality,Mathematics | Journal |
Volume | Issue | ISSN |
339 | 7 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Piotr Borowiecki | 1 | 43 | 8.12 |
Dieter Rautenbach | 2 | 946 | 138.87 |
Christian Löwenstein | 3 | 131 | 16.28 |
Michael Gentner | 4 | 22 | 4.46 |