Improved lower bounds on k‐independence

DOI10.1002/jgt.3190150110zbMath0753.68079OpenAlexW1562917120MaRDI QIDQ3970967

Yair Caro, Zsolt Tuza

Publication date: 25 June 1992

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.3190150110

zbMATH Keywords

\(k\)-independence\(r\)-uniform hypergraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10)

Related Items (32)

Independence in uniform linear triangle-free hypergraphs ⋮ A probabilistic lower bound on the independence number of graphs ⋮ Mixed domination and 2-independence in trees ⋮ On Subgraphs of Bounded Degeneracy in Hypergraphs ⋮ Streaming algorithms for independent sets in sparse hypergraphs ⋮ Linear-Time Approximation Algorithms for the Max Cut Problem ⋮ Conjecture of TxGraffiti: Independence, domination, and matchings ⋮ Partial Resampling to Approximate Covering Integer Programs ⋮ On the \(k\)-residue of disjoint unions of graphs with applications to \(k\)-independence ⋮ On vertex independence number of uniform hypergraphs ⋮ Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth ⋮ The k‐path vertex cover: General bounds and chordal graphs ⋮ Choice functions ⋮ Extremal problems in hypergraph colourings ⋮ New results on \(k\)-independence of hypergraphs ⋮ Partitions of graphs into small and large sets ⋮ Independence numbers of hypergraphs with sparse neighborhoods. ⋮ \(k\)-domination and \(k\)-independence in graphs: A survey ⋮ On a polynomial fractional formulation for independence number of a graph ⋮ Constructing test functions for global optimization using continuous formulations of graph problems ⋮ Generalising Fisher's inequality to coverings and packings ⋮ On the Independence Number of Steiner Systems ⋮ The potential of greed for independence ⋮ Covering the cliques of a graph with vertices ⋮ New results on \(k\)-independence of graphs ⋮ On approximation of the vertex cover problem in hypergraphs ⋮ Linear kernelizations for restricted 3-Hitting Set problems ⋮ Independent sets in bounded-degree hypergraphs ⋮ MAX for \(k\)-independence in multigraphs ⋮ Independent \((k + 1)\)-domination in \(k\)-trees ⋮ 3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size ⋮ Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees

This page was built for publication: Improved lower bounds on k‐independence