ISGCI project home All classes Smallgraphs

Graphclass: bipartite permutation

Equivalent classes: AT-free bipartite (T₂,X₂,X₃,hole,triangle)-free bipartite tolerance
Complement classes: (3K₁,co-(T₂),co-(X₂),co-(X₃),anti-hole)-free
Related classes: bipartite permutation

Inclusions

Minimal superclasses: AT-free (C₆,C₈,T₂,X₃,co-(BW₃),co-(W₅),co-(W₇),co-(X₁₀₃),co-(X₁₀₅),co-(X₁₀₆),co-(X₁₀₇),co-(X₁₀₈),co-(X₁₀₉),co-(X₁₁₀),co-(X₁₁₁),co-(X₁₁₂),co-(X₁₁₃),co-(X₁₁₄),co-(X₁₁₅),co-(X₁₁₆),co-(X₁₁₇),co-(X₁₁₈),co-(X₁₁₉),co-(X₁₂₀),co-(X₁₂₁),co-(X₁₂₂),co-(X₁₂₃),co-(X₁₂₄),co-(X₁₂₅),co-(X₁₂₆),co-(X₅₃),co-(X₈₈),co-X₁₀₄)-free (C_n+6,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₅,X₃₆,X₃₇,X₃₈,X₃₉,X₄₀,X₄₁,XF₂ⁿ⁺¹,XF₃ⁿ,XF₄ⁿ)-free (C_n+6,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₅,X₃₆,XF₂ⁿ⁺¹,XF₃ⁿ,XF₄ⁿ,co-XF₁²ⁿ⁺³,co-XF₅²ⁿ⁺³,co-XF₆²ⁿ⁺²,odd anti-hole)-free (C_n+6,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₆,XF₁²ⁿ⁺³,XF₂ⁿ⁺¹,XF₃ⁿ,XF₄ⁿ,XF₅²ⁿ⁺³,XF₆²ⁿ⁺²,co-(C_n+6),co-(T₂),co-(X₂),co-(X₃),co-(X₃₀),co-(X₃₁),co-(X₃₂),co-(X₃₃),co-(X₃₄),co-(X₃₆),co-XF₁²ⁿ⁺³,co-XF₂ⁿ⁺¹,co-XF₃ⁿ,co-XF₄ⁿ,co-XF₅²ⁿ⁺³,co-XF₆²ⁿ⁺²,odd anti-hole)-free (C_n+6,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₆,XF₁²ⁿ⁺³,XF₂ⁿ⁺¹,XF₃ⁿ,XF₄ⁿ,XF₅²ⁿ⁺³,XF₆²ⁿ⁺²,co-(C_n+6),co-(T₂),co-(X₂),co-(X₃),co-(X₃₀),co-(X₃₁),co-(X₃₂),co-(X₃₃),co-(X₃₄),co-(X₃₆),co-XF₁²ⁿ⁺³,co-XF₂ⁿ⁺¹,co-XF₃ⁿ,co-XF₄ⁿ,co-XF₅²ⁿ⁺³,co-XF₆²ⁿ⁺²,odd-hole)-free HHG-free (T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₅,X₃₆,XF₂ⁿ⁺¹,XF₃ⁿ,XF₄ⁿ,anti-hole,co-XF₁²ⁿ⁺³,co-XF₅²ⁿ⁺³,co-XF₆²ⁿ⁺²,hole)-free (XF₁²ⁿ⁺³,XF₅²ⁿ⁺³,XF₆²ⁿ⁺²,co-(T₂),co-(X₂),co-(X₃),co-(X₃₀),co-(X₃₁),co-(X₃₂),co-(X₃₃),co-(X₃₄),co-(X₃₅),co-(X₃₆),anti-hole,co-XF₂ⁿ⁺¹,co-XF₃ⁿ,co-XF₄ⁿ,hole)-free (anti-hole,co-sun,hole)-free biconvex bipartite co-trapezoid circle graph with equator circle-polygon circular convex bipartite co-comparability co-comparability comparability co-perfectly orderable co-permutation comparability weakly chordal comparability graphs of dimension 2 posets comparability graphs of dimension 4 posets comparability graphs of posets of interval dimension 2, height 1 containment graph of intervals domination modular open-neighbourhood-Helly permutation pseudo-modular triangle-free spider graph unimodular
Maximal subclasses: (2C₄,3K₂,C₆,E,P₂ cup

P₄,P₆,X₂₅,X₂₆,X₂₇,X₂₈,X₂₉,odd-cycle)-free (2K₂,C₅,triangle)-free (2K₂,odd-cycle)-free 2K₂-free bipartite (T₂,cycle)-free bipartite bithreshold bipartite chain caterpillar difference

Problems summary

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

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded [1182]
See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from permutation [1164]
Polynomial [O(V^5E^3)] from Berge bull-free [1278]
Polynomial [O(n logn logn)] from trapezoid

Timebound valid only when given the model [1120] ; otherwise O(n^2).

Polynomial from parity [170]
Polynomial [O(n^4)] from AT-free [160]
Polynomial from bipartite

Variant of matching.

Polynomial [O(n^2)] from circle [1121]
Polynomial from interval filament [1159]
Polynomial [O(n^{6p+2})] from (p,q<=2)-colorable [1116]
Polynomial from perfect [476]
Polynomial from nearly bipartite
Polynomial [O(V^4)] from weakly chordal [997]
Polynomial from subtree overlap [1123]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Linear from co-comparability [1100]
Polynomial from Gallai [1081]
Polynomial from comparability [453]
Polynomial [O(VE)] from weakly chordal [530] [1119]
Polynomial from Meyniel [169]
Polynomial from clique separable [1081]
See also : Weighted independent set

Algorithms for Domination

Linear [O(V)] from permutation [1342] [1147] [1148] [1149] [1165]
Polynomial from k-polygon [352]
Polynomial from co-comparability [1150] [1151]
Polynomial from convex [1167]
Polynomial from AT-free [1152]
Polynomial [O(n^2 log^5 n)] from co-bounded tolerance [1172]

Assuming a square embedding of the graph is given; finding this is an open problem.

Polynomial from trapezoid [1155]
Polynomial from probe interval [1340]
See also : Cliquewidth expression