ISGCI project home  All classes  Smallgraphs

Graphclass: P4-bipartite

Definition:
A graph is P4-bipartite if its vertex set can be partitioned in two subsets, each of which induces a  P4-free  graph.

References: [568] [1310]
Complement classes: self-complementary

Inclusions

Maximal subclasses:  (1,2)-polar   (2K2,C4)-free   (2K3,2P3,C5,C6,C7,K2,3,K3 cup P3,X84,co-(3K2),co-(C4 cup P2),co-(C6),co-(P2 cup P4),co-(P6),co-(X18),co-(X5),co-antenna,co-domino,co-fish)-free   (3K2,C4 cup P2,C5,C6,K2 cup K3,K3,3,K3,3+e,P2 cup P4,P6,X18,X5,co-(2P3),co-(C6),co-(C7),co-(X84),antenna,domino,fish)-free   (5,2)-crossing-chordal   (5,2)-odd-crossing-chordal   (C5,C6,C7,C8,P8,X19,X20,X21,X22,gem,house)-free   (C5,P,P5,S3,co-(P),co-fork,fork,house,net)-free   C5-free cap P4-tidy   (Cn+4,S3,claw,net)-free   (Cn+4,XF2n+1,XF3n,claw)-free   HHDG-free   P4-brittle   P4-extendible   P4-extendible cap P4-sparse   P4-lite   P4-reducible   (P5,anti-hole,co-gem)-free   (S3,co-(Cn+4),co-claw,net)-free   (S3,claw,net)-free cap chordal   (co-(Cn+4),co-XF2n+1,co-XF3n,co-claw)-free   almost tree (1)   astral triple-free   cactus   chordal cap unit circular arc   claw-free cap interval   co-P4-brittle   distance-hereditary   (domino,gem,house)-free cap pseudo-modular   hereditary N*-perfect   indifference   parity   planar of degree 3   proper interval   pseudo-split   unit interval   weak bisplit 

Problems summary

Recognition:NP-completedetails
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth:Unboundeddetails
Weighted independent set:NP-completedetails
Independent set:NP-completedetails
Domination:NP-completedetails

Algorithms for Recognition

NP-complete [4] [568]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from bipartite permutation  [1182]
Unbounded from (2K2,co-(C6),odd anti-cycle)-free 
     From the complement .



Unbounded from Hn,q grid  [1176]
Unbounded from co-comparability graphs of posets of interval dimension 2, height 1 
     See  comparability graphs of posets of interval dimension 2, height 1  .


Unbounded from (co-(Cn+4),co-XF2n+1,co-XF3n,co-claw)-free 
     From the complement .


Unbounded from unit interval  [1177]

Unbounded from co-P4-brittle 
     See  P4-brittle 


Unbounded from split  [1176]
Unbounded from (S3,co-(Cn+4),co-claw,net)-free 
     From the complement .





Unbounded from C4-free cap C6-free cap bipartite  [1183]




Unbounded from co-bipartite 
     See  bipartite  .

Unbounded from grid  [1177]

Unbounded from (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free 
     From the complement .








See also : Cliquewidth expression

Algorithms for Weighted independent set

NP-complete from planar of degree 3  [421]
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 2-subdivision 
     From Poljak's [1111] construction (which is a 2-subdivision). See also [453]

See also : Weighted independent set

Algorithms for Domination

NP-complete from chordal bipartite  [1156]
NP-complete from planar of degree 3  [420]
NP-complete from bipartite  [1142]
NP-complete from partial grid  [1162] [630]
NP-complete from split  [1144] [1145]
See also : Cliquewidth expression