ISGCI project home  All classes  Smallgraphs

Graphclass: (2,0)-colorable

References: [1116] [142]
Equivalent classes:  co-bipartite   odd anti-cycle-free 
Complement classes:  (0,2)-colorable   bipartite   bisplit cap triangle-free   odd-cycle-free   perfect cap triangle-free 
Related classes:  (2,0)-colorable cap chordal   (p,q)-colorable 

Inclusions

Minimal superclasses:  2-split cap perfect   (2P3,3K2,C4 cup P2,C6,K2,3,P6,X130,X132,X134,X152,X153,X154,X155,X156,X157,X158,X18,X84,co-(X11),co-(X127),co-(X128),co-(X129),co-(X131),co-(X133),co-(X135),co-(X136),co-(X137),co-(X138),co-(X139),co-(X140),co-(X141),co-(X142),co-(X143),co-(X144),co-(X145),co-(X146),co-(X147),co-(X148),co-(X149),co-(X150),co-(X151),co-(X30),co-(X35),co-(X46),co-XF12n+3,co-XF62n+3,co-antenna,co-eiffeltower,co-longhorn,domino,fish,odd anti-hole)-free   (4K1,odd anti-hole,odd-hole)-free   4K1-free   AT-free cap claw-free   Berge   Berge cap bull-free   Berge cap claw-free   (C5,P5)-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,XF2n+1,XF3n,XF4n,co-XF12n+3,co-XF52n+3,co-XF62n+2,odd anti-hole)-free   (Cn+6,X37,claw,co-antenna,net,sun)-free   Gallai-perfect   Hamiltonian hereditary   (K2,3,P,P5)-free   (K2,3,P,hole)-free   (K2,3,P5)-free   (P5,co-(X38),co-gem)-free   (P5,bull,odd anti-hole)-free   (P5,bull)-free   (P5,claw)-free   P5-free   (S3,claw,net)-free   (X12,X5,X95,X96,X97,co-(X12),co-(X5),co-(X95),co-(X96),co-(X97),co-(claw cup triangle),claw cup triangle,co-cricket,co-twin-house,cricket,odd anti-hole,odd-hole,twin-house)-free   cal C(G)-perfect   (co-(W4),co-(W5),co-butterfly)-free   bipartite cup co-bipartite cup co-line graphs of bipartite graphs cup line graphs of bipartite graphs   (bull,fork)-free   (bull,odd anti-hole,odd-hole)-free   bull-free   bull-free cap perfect   (claw,net)-free   (claw,odd anti-hole,odd-hole)-free   claw-free   claw-free cap perfect   co-Gallai   co-comparability   (co-diamond,odd anti-hole)-free   co-gem-free   (co-paw,odd anti-hole)-free   kernel solvable   (odd anti-hole,odd-hole)-free   odd-hole-free   perfect   perfect connected-dominant   perfectly 1-transversable   sun-free 
Maximal subclasses:  (2,0)-colorable cap chordal   (2K2,co-(C6),odd anti-cycle)-free   (3K1,C4,C5)-free   (3K1,C5,K5 - e,co-(C6 cup K1),co-(C7),co-(K3,3 cup K1),co-(K3,3-e cup K1),co-(domino cup K1))-free   (3K1,C5,butterfly,diamond)-free   (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free   (C4,odd anti-cycle)-free   (co-(A),co-(T2),odd anti-cycle)-free   (co-(T3),co-(X81),co-cycle)-free   (co-(star1,2,3),odd anti-cycle)-free   (anti-hole,odd anti-cycle)-free   circular arc cap co-bipartite   co-comparability graphs of posets of interval dimension 2, height 1   co-cycle-free 

Problems summary

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

Algorithms for Recognition


Linear from co-bipartite 
     From the complement  bipartite  .


Linear from odd anti-cycle-free 
     From the complement .


Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from (2K2,co-(C6),odd anti-cycle)-free 
     From the complement .


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-bipartite 
     See  bipartite  .


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






See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from AT-free cap claw-free  [1157]
Polynomial [O(VE)] from (P5,fork)-free  [1125]
Polynomial [O(n^5)] from (K1,4,P5)-free  [1110]
Polynomial from (K2,3,P5)-free  [1110]
Polynomial [O(V^5E^3)] from Berge cap bull-free  [1278]
Polynomial from (P5,cricket)-free  [1110]
Polynomial from (P,P5)-free  [1353]
Polynomial from K2 cup claw-free  [1290]
Polynomial [O(VE)] from co-gem-free 
     Because for all v: G[\co{N}(v)] is P_4-free

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 [O(n^4)] from AT-free  [160]
Polynomial [O(n^8)] from (K4,4,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial from (K2,3,P,hole)-free  [1107]
Polynomial from 4K1-free 
Polynomial from interval filament  [1159]
Polynomial [O(n^{6p+2})] from (p,q<=2)-colorable  [1116]
Polynomial from (K1,4,P,P5,fork)-free  [1103]
Polynomial [O(n^4)] from (P5,claw)-free  [1110]
Polynomial from claw-free  [783]
Polynomial from perfect  [476]
Polynomial from (P5,X82,X83)-free  [1246]
Polynomial [O(VE)] from (bull,fork)-free  [1124] [307]
Polynomial from (K2,3,P,P5)-free  [1107]
Polynomial from subtree overlap  [1123]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Linear from co-comparability  [1100]
Polynomial from claw-free  [947]
Polynomial from co-hereditary clique-Helly  [1298]
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 [O(VE)] from (claw,net)-free  [1127] [515]
Polynomial from (P,T2)-free  [1305]
Polynomial [O(nm)] from (K3,3-e,P5,X98)-free  [1117]
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

Polynomial from co-comparability  [1150] [1151]
Polynomial from AT-free  [1152]
Polynomial [O(VE)] from (claw,net)-free  [1127]
See also : Cliquewidth expression