ISGCI project home  All classes  Smallgraphs

Graphclass: (0,2)-colorable

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

Inclusions

Minimal superclasses:  (2,2)-colorable   2-split   (2K3 + e,co-(X98),house)-free   (2K3 + e,co-(X99),house)-free   (2K3 + e,house)-free   (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   (5,2)   (5,2)-odd-crossing-chordal   (5,2)-odd-noncrossing-chordal   Berge cap bull-free   (C5,house)-free   C5-free   Gallai   Gallai-perfect   (K2 cup K3,X11,X127,X128,X129,X131,X133,X135,X136,X137,X138,X139,X140,X141,X142,X143,X144,X145,X146,X147,X148,X149,X150,X151,X30,X35,X46,XF12n+3,XF62n+3,co-(2P3),co-(3K2),co-(C4 cup P2),co-(C6),co-(P6),co-(X130),co-(X132),co-(X134),co-(X152),co-(X153),co-(X154),co-(X155),co-(X156),co-(X157),co-(X158),co-(X18),co-(X84),antenna,co-domino,co-fish,eiffeltower,longhorn,odd-hole)-free   (K2 cup K3,co-(P),anti-hole)-free   (K2 cup K3,co-(P),house)-free   (K2 cup K3,house)-free   (K3 cup P3,co-(C6),co-(P),co-(P7),co-(X37),co-(X41))-free   (K4,odd anti-hole,odd-hole)-free   K4-free cap perfect   (S3,co-(3K2),co-(E),co-(P2 cup P4))-free   (S3,co-(Cn+6),co-(X37),antenna,co-claw,co-sun)-free   (S3,co-claw,net)-free   (S3,co-claw)-free   (W4,W5,butterfly)-free   (W4,gem)-free   (W4,gem)-free cap short-chorded   (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   (X30,XZ1,XZ4,longhorn)-free   (co-(A),co-(P6),co-domino)-free   co-(BW3)-free   (co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X35),co-(X36),co-(X37),co-(X38),co-(X39),co-(X40),co-(X41),co-XF2n+1,co-XF3n,co-XF4n)-free   (co-(E),co-(P))-free   (co-(K1,4),co-(P),co-fork,house)-free   (co-(K1,4),house)-free   co-(K1,4)-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   bipartite cup co-bipartite cup co-line graphs of bipartite graphs cup line graphs of bipartite graphs   bisplit   (bull,co-fork)-free   (bull,house,odd-hole)-free   (bull,house)-free   (bull,odd anti-hole,odd-hole)-free   bull-free cap perfect   clique-perfect cap triangle-free   (co-claw,house)-free   (co-claw,odd anti-hole,odd-hole)-free   (co-claw,odd anti-hole)-free   (co-claw,odd-hole)-free   (co-cricket,house)-free   (co-fork,house)-free   co-sun-free   (diamond,odd-hole)-free   diamond-free   diamond-free cap perfect   hereditary clique-Helly   hereditary maximal clique irreducible   house-free   i-triangulated   nearly bipartite   odd co-sun-free   (odd-hole,paw)-free   parity   paw-free   paw-free cap perfect   perfect cap split-neighbourhood   probe split   sun-free   totally unimodular   triangle-free   unimodular 
Maximal subclasses:  1-bounded bipartite   2-bounded bipartite   (2K2,C5,triangle)-free   (2K2,odd-cycle)-free   2K2-free cap bipartite   (A,T2,odd-cycle)-free   (C4,C6,odd-cycle)-free   C4-free cap C6-free cap bipartite   (C5,C6 cup K1,C7,K3,3 cup K1,K3,3-e cup K1,co-(K5 - e),domino cup K1,triangle)-free   (C5,co-butterfly,co-diamond,triangle)-free   (E,odd-cycle)-free   E-free cap bipartite   (P7,odd-cycle,star1,2,3,sunlet4)-free   X-chordal cap bipartite   X-conformal cap bipartite   bi-cograph   bipartite cap boxicity 2   bipartite cap co-trapezoid   bipartite cap grid intersection   bipartite chain   circular convex bipartite   comparability graphs of posets of interval dimension 2, height 1   difference   modular   (odd-cycle,star1,2,3)-free   perfect elimination bipartite   probe interval bigraph   pseudo-modular cap triangle-free 

Problems summary

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

Algorithms for Recognition

Linear from bipartite 

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from bipartite permutation  [1182]
Unbounded from C4-free cap C6-free cap bipartite  [1183]
Unbounded from grid  [1177]
See also : Cliquewidth expression

Algorithms for Weighted independent set

Polynomial [O(V^5E^3)] from Berge cap bull-free  [1278]
Polynomial from parity  [170]
Polynomial from bipartite 
     Variant of matching.

Polynomial [O(n^{6p+2})] from (p,q<=2)-colorable  [1116]
Polynomial from perfect  [476]
Polynomial from nearly bipartite 
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Polynomial from Gallai  [1081]
Polynomial from comparability  [453]
Polynomial from Meyniel  [169]
Polynomial from clique separable  [1081]
See also : Weighted independent set

Algorithms for Domination

NP-complete from chordal bipartite  [1156]
NP-complete from bipartite  [1142]
NP-complete from partial grid  [1162] [630]
See also : Cliquewidth expression