Edge density and independence ratio in triangle-free graphs with maximum degree three
type: Item
instance of: scholarly article
title: Edge density and independence ratio in triangle-free graphs with maximum degree three
zbMATH Open document ID: 0856.05056
DOI: 10.1016/0012-365X(94)00263-I
author: J. Griggs
author: O. J. Murphy
published in: Discrete Mathematics
publication date: 1999-03-09T00:00:00Z
review text: Let \(G = (V,E)\) be a graph, and let \(n = |V(G) |\) and \(m = |E(G) |\) be the number of vertices and number of edges in \(G\), respectively. The edge density of \(G\) is defined by \(c = m/n\). An independent set of a graph \(G\) is a set \(S\) of vertices such that no two vertices of \(S\) are adjacent in \(G\). The independence number of a graph \(G\) is the largest number of pairwise nonadjacent vertices in \(G\). The authors present a simple polynomial-time algorithm to compute independent sets of guaranteed size in connected triangle-free noncubic graphs with maximum degree 3. The size of the independent set computed by the algorithm increases as the edge density decreases from 3/2 to 1, thereby establishing new lower bounds of the independence number of these graphs.
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 897575
zbMATH Keywords: edge density
zbMATH Keywords: independent set
zbMATH Keywords: independence number
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: triangle-free noncubic graphs
MaRDI profile type: Publication
cites work: Q4111622
cites work: Largest bipartite subgraphs in triangle-free graphs with maximum degree three
cites work: Q5782525
cites work: Q3863917
cites work: Lower bounds on the independence number in terms of the degrees
cites work: Bipartite density and the independence ratio
cites work: Computing independent sets in graphs with large girth
cites work: Some Ramsey-Type Numbers and the Independence Ratio
description: scientific article; zbMATH DE number 897575