2018/07/13 by Francetić, Nevena, Herke, Sara, Horsley, Daniel
#05C69 (Primary) 05B40 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1807.04997
For a fixed positive integer k, a set S of vertices of a graph or multigraph is called a k-independent set if the subgraph induced by S has maximum degree less than k. The well-known algorithm MAX finds a maximal k-independent set in a graph or multigraph by iteratively removing vertices of maximum degree until what remains has maximum degree less than k. We give an efficient procedure that determines, for a given degree sequence D, the smallest cardinality b(D) of a k-independent set that can result from any application of MAX to any loopless multigraph with degree sequence D. This analysis of the worst case is sharp for each degree sequence D in that there exists a multigraph G with degree sequence D such that some application of MAX to G will result in a k-independent set of cardinality exactly b(D).