ISGCI project home  All classes  Smallgraphs

Graphclass: 1-bounded bipartite

Definition:
A  bipartite  graph (X,Y,E) is 1-bounded bipartite if every vertex in X, resp. Y, has at most 1 non-neighbour in Y, resp. X.

References: [1262]
Equivalent classes:  (C5,co-butterfly,co-diamond,triangle)-free 
Complement classes:  (3K1,C5,butterfly,diamond)-free 
Related classes:  1-bounded tripartite   2-bounded bipartite 

Inclusions

Minimal superclasses:  (0,2)-colorable   2-bounded bipartite   (3K2,co-(P),co-gem,house)-free   (A cup K1,co-(K1,4),co-(W4),co-(W5),co-4-fan,co-fork cup K1,gem cup K1,net cup K1)-free   (A,C4 cup 2K1,P2 cup P3,R,co-(K5 - e),co-(W5),co-claw,twin-C5,twin-house)-free   (A,C4 cup 2K1,P2 cup P3,R,co-(K5 - e),co-claw,odd anti-hole,twin-house)-free   (C5,C6 cup K1,C7,K3,3 cup K1,K3,3-e cup K1,co-(K5 - e),domino cup K1,triangle)-free   (C5,P2 cup P3,house)-free   (C5,P6,co-(P6))-free   (C5,bull,co-gem,gem)-free   (C5,co-gem,gem)-free   (C5,co-gem,house)-free   (E,odd-cycle)-free   E-free cap bipartite   (K2 cup K3,co-(P),co-(X163),co-(X95),co-diamond,house)-free   (K2 cup K3,co-diamond)-free   (P2 cup P3,house)-free   P6-free cap tripartite   (P7,odd-cycle,star1,2,3,sunlet4)-free   (co-(K1,4),co-diamond)-free   (co-(P),butterfly,fork,gem)-free   (co-(W4),co-(W5),co-butterfly)-free   (co-(W4),co-claw,co-gem,odd anti-hole)-free   (co-(W4),co-claw,co-gem)-free   (co-(W4),co-claw)-free   co-(XC10)-free   bi-cograph   bipartite   bisplit cap triangle-free   (bull,co-fork,co-gem)-free   (bull,co-fork,fork)-free   (bull,co-gem,gem)-free   (bull,fork)-free   (co-claw,co-diamond,odd anti-hole)-free   (co-claw,co-diamond)-free   (co-diamond,diamond)-free   (co-diamond,house)-free   (co-diamond,odd anti-hole)-free   (co-gem,house)-free   co-gem-free   co-line graphs of bipartite graphs   (fork,odd-cycle)-free   fork-free   murky   odd-cycle-free   perfect cap triangle-free   triangle-free 

Problems summary

Recognition:Polynomialdetails
Cliquewidth expression:Lineardetails
Cliquewidth:Boundeddetails
Weighted independent set:Lineardetails
Independent set:Lineardetails
Domination:Lineardetails

Algorithms for Recognition


Polynomial from (C5,co-butterfly,co-diamond,triangle)-free 
     Finite forbidden subgraph characterization

Algorithms for Cliquewidth expression

Linear from (bull,fork,gem)-free  [1185]
Linear from (co-(P),fork,gem)-free  [1184] [1185]
Linear from (bull,co-fork,fork)-free  [1124] [1185]
Linear from (co-diamond,diamond)-free  [1126]
Linear from (bull,fork,house)-free  [1124] [1185]
Linear from (P7,odd-cycle,star1,2,3)-free  [1181]
Linear from (co-(P),fork,house)-free  [1185] [1186]
Polynomial [O(n^2+nm)] from (odd-cycle,star1,2,3)-free  [1140]
Polynomial [O(n^2+nm)] from (odd-cycle,star1,2,3,sunlet4)-free  [1139]
See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth





Bounded from cliquewidth 4 
Bounded from (co-gem,gem)-free  [1188] [1185]

Bounded from (co-gem,house)-free 
     From the complement .


Bounded from (bull,co-fork,co-gem)-free 
     From the complement .

Bounded from (C5,co-gem,house)-free 
     From the complement .

Bounded from (3K2,co-(P),co-gem,house)-free 
     From the complement .



Bounded from (co-diamond,house)-free 
     From the complement .






Bounded from (A,T2,odd-cycle)-free  [1183]


See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from (co-diamond,diamond)-free  [1126]
Polynomial [O(VE)] from (co-(P),fork)-free  [1125]
Polynomial [O(V^5E^3)] from Berge cap bull-free  [1278]
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 from parity  [170]
Polynomial from bipartite 
     Variant of matching.

Polynomial from (co-(P),butterfly,fork,gem)-free  [1104]
Polynomial [O(n^{6p+2})] from (p,q<=2)-colorable  [1116]
Polynomial from perfect  [476]
Polynomial from nearly bipartite 
Polynomial [O(VE)] from (bull,fork)-free  [1124] [307]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Polynomial from Gallai  [1081]
Polynomial from co-hereditary clique-Helly  [1298]
Polynomial from comparability  [453]
Polynomial from Meyniel  [169]
Polynomial from clique separable  [1081]
Open from (E,odd-cycle)-free  [1351]
See also : Weighted independent set

Algorithms for Domination

See also : Cliquewidth expression