ISGCI project home  All classes  Smallgraphs

Graphclass: (2K2,C4)-free

References: [758]
Equivalent classes:  pseudo-split 
Complement classes: self-complementary
See also: 2K2 C4

Inclusions

Minimal superclasses:  (2K2,co-(P6))-free   (2K2,house)-free   (2K3 + e,co-(X98),house)-free   (2K3 + e,co-(X99),house)-free   (2K3 + e,house)-free   (2K3,house)-free   (2K4,house)-free   (6,1)-even-chordal   (A,P6,domino)-free   BW3-free   (C4,P5)-free   (C4,P6)-free   (C6,K3,3+e,P,P7,X37,X41)-free   (C6,co-(C6))-free   (C6,house)-free   (E,P)-free   (K2 cup K3,co-(P),house)-free   (K2 cup K3,house)-free   K2 cup K3-free   K2 cup claw-free   (K2,3,P,P5)-free   (K2,3,P5)-free   K2,3-free   (K3 cup P3,co-(C6),co-(P),co-(P7),co-(X37),co-(X41))-free   (K3,3,P5)-free   (K3,3-e,P5,X98)-free   (K3,3-e,P5,X99)-free   (K3,3-e,P5)-free   (K4,4,P5)-free   (P,P5)-free   (P,P7)-free   (P,P8)-free   (P,T2)-free   (P,star1,2,3)-free   (P,star1,2,4)-free   (P,star1,2,5)-free   (P2 cup P3,house)-free   P4-bipartite   (P5,X82,X83)-free   (P5,co-(C6))-free   (P5,co-(P2 cup P3))-free   (P5,house)-free   P5-free   (P6,X30,X8)-free   P7-free   (X30,XZ1,XZ4,longhorn)-free   (X79,X80)-free   (co-(A),co-(P6),co-domino)-free   co-(BW3)-free   (co-(E),co-(P))-free   co-(K2 cup claw)-free   (co-(P),co-(P7))-free   (co-(P),co-(P8))-free   (co-(P),co-(T2))-free   (co-(P),co-(star1,2,3))-free   (co-(P),co-star1,2,4)-free   (co-(P),co-star1,2,5)-free   (co-(P),house)-free   (co-(P6),co-(X30),co-(X8))-free   (co-(X30),co-(XZ1),co-(XZ4),co-longhorn)-free   (co-(X79),co-(X80))-free   (co-(X82),co-(X83),house)-free   even anti-cycle-free   even anti-hole-free   even-cycle-free   even-hole-free   extended P4-laden   house-free 
Maximal subclasses:  (1,1)-colorable   (2K2,C4,C5,H,S3,X160,co-(X159),net,rising sun)-free   (2K2,C4,C5,S3,X159,X160,co-(H),co-rising sun,net)-free   (2K2,C4,C5,S3,net,rising sun)-free   (2K2,C4,C5,co-sun)-free   (2K2,C4,C5)-free   chordal cap co-chordal   probe threshold cap split   split 

Problems summary

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

Algorithms for Recognition

Linear [758]
Polynomial
     Finite forbidden subgraph characterization

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from split  [1176]
See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear
Polynomial from nK2-free, fixed n  [1102]
Polynomial from (K2,3,P5)-free  [1110]
Polynomial from (P,P5)-free  [1353]
Polynomial [O(n^4)] from (C4,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial from K2 cup claw-free  [1290]
Polynomial from (P5,house)-free  [1109]
Polynomial [O(n^6)] from (K3,3,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial [O(n^8)] from (K4,4,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial from (P5,X82,X83)-free  [1246]
Polynomial from 2K2-free  [1160]
Polynomial from (K2,3,P,P5)-free  [1107]
Polynomial from (C4,P6)-free  [1353]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Linear from extended P4-laden  [438]
Polynomial from (C4,P6)-free  [1351] [1352]
Polynomial from (K3,3-e,P5)-free  [1246]
Polynomial [O(VE)] from (P,P5)-free  [1117]
Polynomial from (E,P)-free  [1305]
Polynomial from (K2,3,P,P5)-free  [1346] [1107]
Polynomial [O(V^8)] from (P,P7)-free  [1351]
Polynomial from (C6,K3,3+e,P,P7,X37,X41)-free  [1346]
Polynomial from (P,T2)-free  [1305]
Polynomial [O(nm)] from (K3,3-e,P5,X98)-free  [1117]
Polynomial from (P5,co-(P2 cup P3))-free  [1350]
Polynomial from (P,star1,2,5)-free  [1349]
Polynomial [O(V^{5})] from (K3,3-e,P5,X99)-free  [1307]
Polynomial from (P,P8)-free  [1306]
Open from (P,star1,2,3)-free  [1351]
Open from (P,star1,2,4)-free  [1351] [1306]
See also : Weighted independent set

Algorithms for Domination

NP-complete from split  [1144] [1145]
See also : Cliquewidth expression