ISGCI project home  All classes  Smallgraphs

Graphclass: XC9-free

Equivalent classes:  matrogenic 
Complement classes: self-complementary
See also: XC9

Inclusions

Minimal superclasses:  (2K3,2K3 + e,co-(A),co-(H),co-(X45),co-(XZ5),co-domino)-free   (2K3,X42,co-(A),co-(H),co-(X45),co-(X46),co-(X47),co-(X48),co-(X49),co-(X50),co-(X51),co-(X52),co-(X53),co-(X54),co-(X55),co-(X56),co-(X57))-free   (2K3,house)-free   (2K4,house)-free   (A,H,K3,3,K3,3-e,X45,XZ5,domino)-free   (A,H,K3,3,X45,X46,X47,X48,X49,X50,X51,X52,X53,X54,X55,X56,X57,co-(X42))-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   (K3 cup P3,co-(C6),co-(P),co-(P7),co-(X37),co-(X41))-free   (P,P5,co-(P),co-fork,fork,house)-free   (P2 cup P3,house)-free   (P5,co-(P2 cup P3))-free   co-(K2 cup claw)-free   domination perfect   extended P4-sparse   unigraph 
Maximal subclasses:  (C5,K2 cup K3,K2,3,P,P2 cup P3,P5,co-(P),co-(P2 cup P3),co-fork,fork,house)-free   C5-free cap matrogenic   matroidal 

Problems summary

Recognition:Lineardetails
Cliquewidth expression:Lineardetails
Cliquewidth:Boundeddetails
Weighted independent set:Lineardetails
Independent set:Lineardetails
Domination:Lineardetails

Algorithms for Recognition

Linear from matrogenic  [1058]
Polynomial
     Finite forbidden subgraph characterization


Algorithms for Cliquewidth expression

Linear from (P,co-(P),co-fork,fork)-free  [1185]
Linear from partner-limited  [1179]
Linear from semi-P4-sparse  [1186]
Linear from P4-tidy  [1175]
Linear from (P5,fork,house)-free  [1185] [402]
Linear from (co-(P),fork,house)-free  [1185] [1186]
See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Bounded from (P,P5,co-fork)-free 
     From the complement .


Bounded from cliquewidth 4 


See also : Cliquewidth expression

Algorithms for Weighted independent set

Polynomial [O(VE)] from (co-(P),fork)-free  [1125]
Polynomial [O(VE)] from (P5,fork)-free  [1125]
Polynomial from (K2,3,P5)-free  [1110]
Polynomial from semi-P4-sparse  [402]
Polynomial from (P,P5)-free  [1353]
Polynomial from K2 cup claw-free  [1290]
Polynomial from (P5,house)-free  [1109]
Polynomial from fork-free  [1099]
Polynomial [O(n^6)] from (K3,3,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial from (P5,co-fork)-free  [1161]
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 (K2,3,P,P5)-free  [1107]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Linear from partner-limited  [1180]
Linear from P4-tidy  [440]
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

See also : Cliquewidth expression