Edge density and independence ratio in triangle-free graphs with maximum degree three
From MaRDI portal
Publication:1917491
DOI10.1016/0012-365X(94)00263-IzbMath0856.05056MaRDI QIDQ1917491
Jerrold R. Griggs, O. J. Murphy
Publication date: 9 March 1999
Published in: Discrete Mathematics (Search for Journal in Brave)
independence number; independent set; polynomial-time algorithm; edge density; triangle-free noncubic graphs
05C35: Extremal problems in graph theory
Related Items
The Fractional Chromatic Number of \(\boldsymbol{K_{\Delta }}\)-Free Graphs, Randomly colouring graphs (a combinatorial view), Finding independent sets in \(K_4\)-free 4-regular connected graphs, The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\), Bipartite subgraphs of triangle-free subcubic graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing independent sets in graphs with large girth
- Lower bounds on the independence number in terms of the degrees
- Bipartite density and the independence ratio
- Largest bipartite subgraphs in triangle-free graphs with maximum degree three
- Some Ramsey-Type Numbers and the Independence Ratio