Independence, odd girth, and average degree

DOI10.1002/jgt.20518zbMath1218.05116OpenAlexW2000620038MaRDI QIDQ3005112

Dieter Rautenbach, Anders Sune Pedersen, Friedrich Regen, Christian Löwenstein

Publication date: 7 June 2011

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

Full work available at URL: https://www.db-thueringen.de/servlets/MCRFileNodeServlet/dbt_derivate_00018948/IfM_Preprint_M09_32.pdf

zbMATH Keywords

independencestabilitytriangle-free graphodd girth

Mathematics Subject Classification ID

Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (14)

Transversals and independence in linear hypergraphs with maximum degree two ⋮ New bounds on the independence number of connected graphs ⋮ Lower bounds on the independence number of certain graphs of odd girth at least seven ⋮ The maximum spectral radius of \(\{C_3, C_5\}\)-free graphs of given size ⋮ Uniquely restricted matchings in subcubic graphs without short cycles ⋮ Some bounds on the size of maximum G-free sets in graphs ⋮ Independent sets and matchings in subcubic graphs ⋮ An improved lower bound on the independence number of a graph ⋮ Adjacency eigenvalues of graphs without short odd cycles ⋮ Bounds on the independence number of a graph in terms of order, size and maximum degree ⋮ A better lower bound on average degree of online \(k\)-list-critical graphs ⋮ Minimum \(k\)-path vertex cover ⋮ The Fano Plane and the Strong Independence Ratio in Hypergraphs of Maximum Degree 3 ⋮ New analytical lower bounds on the clique number of a graph

Cites Work

• Independence in graphs with maximum degree four
• On the tightness of the \(\frac {5}{14}\) independence ratio
• The independence number in graphs of maximum degree three
• A note on the independence number of triangle-free graphs. II
• The independence number of dense graphs with large odd girth
• The independence number of graphs with large odd girth
• On the chromatic number of triangle-free graphs of large minimum degree
• Foreword: Special issue on stability in graphs and related topics
• Bipartite subgraphs of triangle-free subcubic graphs
• Some Ramsey-Type Numbers and the Independence Ratio
• A new proof of the independence ratio of triangle-free cubic graphs
• On the independence number of a graph in terms of order and size
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Independence, odd girth, and average degree