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 numberindependent setpolynomial-time algorithmedge densitytriangle-free noncubic graphs
Related Items (5)
Finding independent sets in \(K_4\)-free 4-regular connected graphs ⋮ The Fractional Chromatic Number of \(\boldsymbol{K_{\Delta }}\)-Free Graphs ⋮ Randomly colouring graphs (a combinatorial view) ⋮ 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
This page was built for publication: Edge density and independence ratio in triangle-free graphs with maximum degree three
