#### Document Type

Article

#### Publication Date

6-2010

#### Abstract

Let G be an undirected graph with maximum degree at most 3 such that G does not contain either of the two graphs shown in Figure 1 as a subgraph. We prove that the independence number of G is at least n(G)/3 + nt(G)/63, where n(G) is the number of vertices in G and nt(G) is the number of nontriangle vertices in G. We show an application of the aforementioned combinatorial result to the area of parameterized complexity. We present a linear-time kernelization algorithm for the independent set problem on graphs with maximum degree at most 3 that computes a kernel of size at most 630k/211 < 3k, where k is the lower bound on the size of the independent set sought.

#### Recommended Citation

Kanj, Iyad A. and Zhang, Fenghui, "Independent Set on graphs with maximum degree 3" (2010). *Technical Reports*. 14.

http://via.library.depaul.edu/tr/14