Algorithms for Recognition
Polynomial from (K3,3,K4,W4
K1,W5,X86,X87,X88,X89,X90,co-(C7),co-(X38),co-(X39),co-(butterfly K1),co-diamond)-free Definition:
A tripartite
graph is 1-bounded tripartite
if every vertex in partition Xi
has at most 1 non-neighbour in every partition Xj
, i unequal to j.
K1,W5,X86,X87,X88,X89,X90,co-(C7),co-(X38),co-(X39),co-(butterfly K1),co-diamond)-free K1),co-(W5),co-(X86),co-(X87),co-(X88),co-(X89),co-(X90),butterfly K1,diamond)-free P4,net)-free (A K1,co-(K1,4),co-(W4),co-(W5),co-4-fan,co-fork K1,gem K1,net K1)-free K2 claw-free (P6,X30,X8)-free P6-free 
tripartite (X30,XZ1,XZ4,longhorn)-free (co-(K1,4),co-diamond)-free (co-(W4),co-gem)-free co-gem-free co-hereditary clique-Helly fork-free | Recognition: | Polynomial | details |
| Cliquewidth expression: | Unknown to ISGCI | details |
| Cliquewidth: | Unknown to ISGCI | details |
| Weighted independent set: | Polynomial | details |
| Independent set: | Polynomial | details |
| Domination: | Unknown to ISGCI | details |
Algorithms for Recognition
Polynomial from (K3,3,K4,W4 K1,W5,X86,X87,X88,X89,X90,co-(C7),co-(X38),co-(X39),co-(butterfly K1),co-diamond)-free
| Finite forbidden subgraph characterization |
Algorithms for Cliquewidth expression
See also
: Cliquewidth : Weighted independent set : Domination
Algorithms for Cliquewidth
See also
: Cliquewidth expression
Algorithms for Weighted independent set
Polynomial from K2 claw-free
[1290]
Polynomial [O(VE)]
from co-gem-free
| Because for all v: G[\co{N}(v)] is P_4-free |
Algorithms for Independent set
Polynomial from co-hereditary clique-Helly
[1298]
See also
: Weighted independent set
Algorithms for Domination
See also
: Cliquewidth expression