HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Complexity of Independent Set on Triangle-Free Planar Cubic Graphs

Submitted by: @import:stackexchange-cs··
0
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!

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.