ISGCI project home All classes Smallgraphs

Graphclass: (2,2)-colorable

References: [1116] [142]
Equivalent classes: 2-split
Related classes: (2,2)-colorable chordal (p,q)-colorable

Inclusions

Minimal superclasses: (p,q<=2)-colorable
Maximal subclasses: (0,2)-colorable (0,2)-colorable chordal (1,2)-colorable (2,2)-colorable chordal 2-split perfect (2K₂,C₄,C₅,S₃,co-rising sun,net)-free (3K₃,C_n+4)-free biconvex bipartite bipartite bridged bisplit triangle-free bithreshold co-bithreshold split comparability split cycle-free odd-cycle-free partial grid perfect triangle-free split superperfect tree

Problems summary

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

Algorithms for Recognition

Polynomial [142]
Polynomial from 2-split [142]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from bipartite permutation [1182]
Unbounded from (2K₂,co-(C₆),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 split [1176]

Unbounded from C₄-free C₆-free bipartite [1183]

Unbounded from co-bipartite

See bipartite .

Unbounded from grid [1177]

Unbounded from (3K₁,co-(T₂),co-(X₂),co-(X₃),anti-hole)-free

From the complement .

See also : Cliquewidth expression

Algorithms for Weighted independent set

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

Algorithms for Independent set

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]
NP-complete from split [1144] [1145]
See also : Cliquewidth expression