I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems.
1) L = set of all (G, k) where G is a graph with maximum degree of at most 4 and contains an independent set of size at least k. Is L in polynomial time or NP-complete?
2) L = set of all (G, k) where G is a graph with max degree 100 containing a clique of at least size k. Is L in P or NP-complete?
Since both Independent Set and Clique are NP-Complete, my first instinct is to say that 1) and 2) are both NP-complete. However, due to the bounded degree restriction, that is likely not true. I am not quite sure what I should be reducing from. Since if I were to attempt to show they are in P, I would have to reduce from something in P and I don't know anything that are remotely similar except Clique and Ind. Set, but like I said, those are NP-complete. I would really appreciate any help I can get with those two proofs. Any proof or hint would be very welcome!
EDIT: Actually after some research it seems that Independent Set problems tend to be NP-Complete when it comes to bounded degree graphs while Clique can usually be found in P-time or even linear time. I am not sure about this case, but it's a start I suppose.