ISGCI project home  All classes  Smallgraphs

Graphclass: 2-subdivision

Definition:
A 2-subdivision of a graph results from inserting 2 new vertices in every edge, that is from replacing each edge uv with a P4 uxyv.
A graph is a 2-subdivision if it is the 2-subdivision of some graph.

Related classes:  2-subdivision cap planar   (C4,C5,C6,C7,C8,H,X85,triangle)-free 

Inclusions

Minimal superclasses:  (C4,C5,C6,C7,C8,H,X85,triangle)-free   caterpillar arboricity <= 2   p-connected   weak bisplit 
Maximal subclasses:  2-subdivision cap planar 

Problems summary

Recognition:Polynomialdetails
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth: Unknown to ISGCI details
Weighted independent set:NP-completedetails
Independent set:NP-completedetails
Domination: Unknown to ISGCI details

Algorithms for Recognition

Polynomial

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

See also : Cliquewidth expression

Algorithms for Weighted independent set

See also : Cliquewidth expression : Independent set

Algorithms for Independent set

NP-complete from 2-subdivision cap planar 
      2-subdivision cap planar  are precisely the 2-subdivision graphs of  planar  graphs.

NP-complete
     From Poljak's [1111] construction (which is a 2-subdivision). See also [453]

See also : Weighted independent set

Algorithms for Domination

See also : Cliquewidth expression