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) Is the 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 in polynomial time or NP-complete?
2) Is the set of all (G, k) where G is a graph with max degree 100 containing a clique of at least size k 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!