ISGCI project home  All classes  Smallgraphs

Graphclass: (C4,odd anti-cycle)-free

Equivalent classes:  (2,0)-colorable cap chordal   (3K1,C4,C5)-free 
Complement classes:  (2K2,C5,triangle)-free   (2K2,odd-cycle)-free   2K2-free cap bipartite   bipartite chain   difference 
See also: odd anti-cycle C4

Inclusions

Minimal superclasses:  (2,0)-colorable   (2,2)-colorable cap chordal   (2P3,3K2,C4 cup P2,C6,K2,3,P6,X130,X132,X134,X152,X153,X154,X155,X156,X157,X158,X18,X84,co-(X11),co-(X127),co-(X128),co-(X129),co-(X131),co-(X133),co-(X135),co-(X136),co-(X137),co-(X138),co-(X139),co-(X140),co-(X141),co-(X142),co-(X143),co-(X144),co-(X145),co-(X146),co-(X147),co-(X148),co-(X149),co-(X150),co-(X151),co-(X30),co-(X35),co-(X46),co-XF12n+3,co-XF62n+3,co-antenna,co-eiffeltower,co-longhorn,domino,fish,odd anti-hole)-free   (2P3,3K2,C4,C5,H,P2 cup P4,P5,S3,X1,X160,co-(X159),co-(X161),co-(X162),co-(X46),co-(X70),net,rising sun)-free   (2P4,A,C5,C6,C7,E,K3,3-e,P7,R,X1,X103,X5,X58,X84,X98,co-(C6),co-(P6),co-(X5),co-(sunlet4),co-antenna,co-domino,co-rising sun,domino,parachute,parapluie,rising sun,twin-house)-free   (3K1,co-(E))-free   (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free   (3K1,house)-free   (3K2,C4 cup P2,C5,P2 cup P4,P5,S3,X1,X46,X70,co-(3K2),co-(C4 cup P2),co-(P2 cup P4),co-(X1),co-(X46),co-(X70),co-fish,co-rising sun,fish,house,net,rising sun)-free   (3K3,Cn+4)-free   (4K1,house)-free   (4K1,odd anti-hole,odd-hole)-free   4K1-free   (A,E,S3,X1,domino,hole,house,net,rising sun)-free   (A,P6,clique wheel,domino,hole,house)-free   AT-free cap chordal   AT-free cap claw-free   Berge cap claw-free   (C4,C5,T2)-free   (C4,C5)-free   (C4,P5)-free   (C4,X91,claw)-free   C4-free cap co-comparability   (C5,P,P5,house)-free   (C5,P2 cup P3,house)-free   (C5,P5,co-(C6),co-(C7),co-(C8),co-(P8),co-(X19),co-(X20),co-(X21),co-(X22),co-gem)-free   (C5,P5,co-(P2 cup P3))-free   (C5,co-gem,house)-free   (Cn+4,H)-free   (Cn+4,P5,bull)-free   (Cn+4,S3 cup K1,claw,net)-free   (Cn+4,S3,claw,net)-free   (Cn+4,T2,X31,XF2n+1,XF3n)-free   (Cn+4,T2,XF2n+1)-free   (Cn+4,T2,net)-free   (Cn+4,X59,longhorn)-free   (Cn+4,XF12n+3,XF62n+2,co-(X34),co-(X36),co-XF2n+1,co-XF3n)-free   (Cn+4,XF2n+1,XF3n,claw)-free   (Cn+4,claw,net)-free   Cn+4-free   (Cn+6,X37,claw,co-antenna,net,sun)-free   Dilworth 2   HHDS-free   HHDbicycle-free   HHP-free   Hamiltonian hereditary   (K2,3,P,P5)-free   (K2,3,P5)-free   (P,co-gem,house)-free   (P2 cup P3,house)-free   P4-indifference   (P5,co-(X38),co-gem)-free   (P5,anti-hole,co-domino,co-gem)-free   (P5,anti-hole,co-gem)-free   (P5,bull,house)-free   (P5,bull,odd anti-hole)-free   (P5,bull)-free cap interval   (P5,claw)-free   (P5,co-domino,co-gem)-free   (P5,fork,house)-free   (S3,claw,net)-free   (S3,claw,net)-free cap chordal   (W4,claw)-free   (co-(E),odd anti-cycle)-free   (co-(P7),co-(star1,2,3),co-(sunlet4),odd anti-cycle)-free   (co-(P7),co-(star1,2,3),odd anti-cycle)-free   (co-(W4),co-(W5),co-butterfly)-free   (co-(W4),co-gem)-free   (co-(star1,2,3),co-(sunlet4),odd anti-cycle)-free   (co-(star1,2,3),odd anti-cycle)-free   (anti-hole,co-domino,odd anti-cycle)-free   (anti-hole,odd anti-cycle)-free   astral triple-free   bipolarizable   boxicity 1   (bull,fork,house)-free   (bull,fork)-free   (bull,house,odd-hole)-free   bull-free   chordal   chordal cap (claw,net)-free   chordal cap co-comparability   chordal cap comparability   chordal cap diametral path   chordal cap dominating pair   chordal cap domination perfect   chordal cap irredundance perfect   chordal cap proper circular arc   chordal cap unit circular arc   (claw,net)-free   (claw,odd anti-hole,odd-hole)-free   (claw,odd anti-hole)-free   (claw,odd-hole)-free   claw-free   claw-free cap interval   claw-free cap perfect   co-bipartite   (co-cricket,house)-free   (co-diamond,house)-free   (co-diamond,odd anti-hole)-free   (co-gem,house)-free   co-gem-free   (co-paw,odd anti-hole)-free   co-probe threshold   hereditary Matula perfect   hereditary Welsh-Powell opposition   hereditary homogeneously orderable   homogeneously representable   (house,hole,domino,sun)-free   indifference   interval   odd anti-cycle-free   proper interval   threshold signed   unit interval 

Problems summary

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

Algorithms for Recognition

Polynomial from (3K1,C4,C5)-free 
     Finite forbidden subgraph characterization


Polynomial from (2,0)-colorable cap chordal  [1249]

Algorithms for Cliquewidth expression

Linear from (P5,bull,house)-free  [1187] [1185]
Linear from (bull,fork,house)-free  [1124] [1185]
Linear from (P5,fork,house)-free  [1185] [402]
See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth








Bounded from (co-(star1,2,3),co-(sunlet4),odd anti-cycle)-free 
     From the complement .




Bounded from (co-(E),odd anti-cycle)-free 
     From the complement .


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

Bounded from (P5,anti-hole,co-domino,co-gem)-free 
     From the complement .



Bounded from co-probe cograph 
     From the complement  probe cograph  .

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






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


Bounded from (co-(star1,2,3),odd anti-cycle)-free 
     From the complement .




Bounded from (2P3,3K2,C4,C5,H,P2 cup P4,P5,S3,X1,X160,co-(X159),co-(X161),co-(X162),co-(X46),co-(X70),net,rising sun)-free 
     From the complement .



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

Bounded from (co-(P7),co-(star1,2,3),co-(sunlet4),odd anti-cycle)-free 
     From the complement .

Bounded from (anti-hole,co-domino,odd anti-cycle)-free 
     From the complement .



Bounded from (co-(P7),co-(star1,2,3),odd anti-cycle)-free 
     From the complement .









Bounded from co-probe threshold 
     From the complement  probe threshold  .




See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from permutation  [1164]
Linear from chordal  [1166]
Linear from AT-free cap claw-free  [1157]
Polynomial [O(VE)] from (P5,fork)-free  [1125]
Polynomial [O(n^5)] from (K1,4,P5)-free  [1110]
Polynomial from (K2,3,P5)-free  [1110]
Polynomial [O(V^5E^3)] from Berge cap bull-free  [1278]
Polynomial from (P5,cricket)-free  [1110]
Polynomial from (P,P5)-free  [1353]
Polynomial [O(n logn logn)] from trapezoid 
     Timebound valid only when given the model [1120] ; otherwise O(n^2).

Polynomial [O(n^4)] from (C4,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

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 (C4,C5,T2)-free  [1108]
Polynomial from (P5,house)-free  [1109]
Polynomial from fork-free  [1099]
Polynomial [O(n^6)] from (K3,3,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial [O(n^4)] from AT-free  [160]
Polynomial [O(n^8)] from (K4,4,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial from (K2,3,P,hole)-free  [1107]
Polynomial [O(n^2)] from circle  [1121]
Polynomial from 4K1-free 
Polynomial from interval filament  [1159]
Polynomial [O(n^{6p+2})] from (p,q<=2)-colorable  [1116]
Polynomial from (K1,4,P,P5,fork)-free  [1103]
Polynomial [O(n^4)] from (P5,claw)-free  [1110]
Polynomial from claw-free  [783]
Polynomial [O(ln)] from circular arc 
     Where l is the minimum number of arcs passing through a given point on the circle. [995]

Polynomial from perfect  [476]
Polynomial from (P5,X82,X83)-free  [1246]
Polynomial from nearly bipartite 
Polynomial [O(VE)] from (bull,fork)-free  [1124] [307]
Polynomial from (K2,3,P,P5)-free  [1107]
Polynomial [O(V^4)] from weakly chordal  [997]
Polynomial from subtree overlap  [1123]
Polynomial from (C4,P6)-free  [1353]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Linear [O(n)] from circular arc  [1105] [1106] [1158]
Linear from co-Matula perfect  [221]
Linear from co-Welsh-Powell perfect  [221]
Linear from co-comparability  [1100]
Linear from chordal  [425] [931]
Polynomial from Gallai  [1081]
Polynomial from (C5,P5,co-(P2 cup P3))-free  [1118]
Polynomial from claw-free  [947]
Polynomial from co-hereditary clique-Helly  [1298]
Polynomial from (C4,P6)-free  [1351] [1352]
Polynomial from comparability  [453]
Polynomial from (K3,3-e,P5)-free  [1246]
Polynomial [O(VE)] from (P,P5)-free  [1117]
Polynomial [O(VE)] from weakly chordal  [530] [1119]
Polynomial from (E,P)-free  [1305]
Polynomial from (K2,3,P,P5)-free  [1346] [1107]
Polynomial [O(V^8)] from (P,P7)-free  [1351]
Polynomial from (C6,K3,3+e,P,P7,X37,X41)-free  [1346]
Polynomial from EPT  [1019]
Polynomial [O(VE)] from (claw,net)-free  [1127] [515]
Polynomial from (P,T2)-free  [1305]
Polynomial from Meyniel  [169]
Polynomial [O(nm)] from (K3,3-e,P5,X98)-free  [1117]
Polynomial from clique separable  [1081]
Polynomial from (P5,co-(P2 cup P3))-free  [1350]
Polynomial from (P,star1,2,5)-free  [1349]
Polynomial [O(V^{5})] from (K3,3-e,P5,X99)-free  [1307]
Polynomial from (P,P8)-free  [1306]
Open from (P,star1,2,3)-free  [1351]
Open from (P,star1,2,4)-free  [1351] [1306]
See also : Weighted independent set

Algorithms for Domination

Linear from dually chordal  [143] [332]
Linear from circular arc  [1143] [1158]
Linear [O(V)] from permutation  [1342] [1147] [1148] [1149] [1165]
Linear from interval  [1143]
Polynomial from strongly chordal  [374]
Polynomial from co-interval cup interval 
     From  interval  and  co-interval  .

Polynomial from directed path  [524]
Polynomial from k-polygon  [352]
Polynomial from co-comparability  [1150] [1151]
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 [O(VE)] from (claw,net)-free  [1127]
Polynomial from trapezoid  [1155]
Polynomial from probe interval  [1340]
See also : Cliquewidth expression