patternMinor
Complexity of Independent Set on Triangle-Free Planar Cubic Graphs
Viewed 0 times
cubicfreeindependentgraphsplanartrianglecomplexityset
Problem
I know that IS (is there independent set of size at least $k$?) on planar cubic graphs is NP-Complete, and IS on triangle-free graphs is also NP-Complete. But how about IS on triangle-free planar cubic graphs? Is it still an NP-Complete problem, or there are some polynomial time solutions?
Any ideas or referrences are appreciated, thank you in advance!
Any ideas or referrences are appreciated, thank you in advance!
Solution
Independent Set is $\mathsf{NP}$-hard even for $3$-connected cubic planar triangle-free graphs, as shown in this nice short note.
Context
StackExchange Computer Science Q#33171, answer score: 6
Revisions (0)
No revisions yet.