ISGCI project home All classes Smallgraphs

Graphclass: (3K₁,co-(T₂),co-(X₂),co-(X₃),anti-hole)-free

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

Inclusions

Minimal superclasses: (2,0)-colorable AT-free claw-free (BW₃,W₅,W₇,X₁₀₃,X₁₀₄,X₁₀₅,X₁₀₆,X₁₀₇,X₁₀₈,X₁₀₉,X₁₁₀,X₁₁₁,X₁₁₂,X₁₁₃,X₁₁₄,X₁₁₅,X₁₁₆,X₁₁₇,X₁₁₈,X₁₁₉,X₁₂₀,X₁₂₁,X₁₂₂,X₁₂₃,X₁₂₄,X₁₂₅,X₁₂₆,X₅₃,X₈₈,co-(C₆),co-(C₈),co-(T₂),co-(X₃))-free Berge bull-free Berge claw-free Bouchet (C₅,P₅)-free (C₆,co-(C₆))-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 (C_n+6,X₃₇,claw,co-antenna,net,sun)-free (K_2,3,P,hole)-free (P₅,co-(C₆))-free (P₅,co-(C₆))-free weakly chordal (P₅,anti-hole,co-gem)-free (P₅,anti-hole)-free (P₅,bull)-free (P₅,claw)-free (T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₅,X₃₆,XF₂ⁿ⁺¹,XF₃ⁿ,XF₄ⁿ,anti-hole,co-XF₁²ⁿ⁺³,co-XF₅²ⁿ⁺³,co-XF₆²ⁿ⁺²,hole)-free (X₁₂,X₅,X₉₅,X₉₆,X₉₇,co-(X₁₂),co-(X₅),co-(X₉₅),co-(X₉₆),co-(X₉₇),co-(claw cup

triangle),claw cup

triangle,co-cricket,co-twin-house,cricket,odd anti-hole,odd-hole,twin-house)-free (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-(X₃₆),co-XF₂ⁿ⁺¹,co-XF₃ⁿ,co-XF₄ⁿ,odd-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 (co-(W₄),co-(W₅),co-butterfly)-free (anti-hole,hole,sun)-free (anti-hole,hole)-free (anti-hole,odd anti-cycle)-free bipartite co-bipartite co-line graphs of bipartite graphs line graphs of bipartite graphs (bull,odd anti-hole,odd-hole)-free bull-free perfect circle circle graph with equator circular arc co-bipartite circular arc comparability (claw,odd anti-hole,odd-hole)-free claw-free perfect co-bipartite co-comparability comparability co-comparability graphs of posets of interval dimension 2, height 1 co-convex-round co-permutation co-tolerance co-trapezoid comparability comparability weakly chordal comparability graphs of dimension 2 posets comparability graphs of posets of interval dimension 2 containment graph of intervals containment graphs convex-round odd anti-cycle-free odd-hole-free perfect connected-dominant permutation sun-free weakly chordal weakly chordal
Maximal subclasses: (2,0)-colorable chordal (3K₁,C₄,C₅)-free (C₄,odd anti-cycle)-free (co-(2C₄),co-(3K₂),co-(C₆),co-(E),co-(P₂ cup

P₄),co-(P₆),co-(X₂₅),co-(X₂₆),co-(X₂₇),co-(X₂₈),co-(X₂₉),odd anti-cycle)-free (co-(T₂),co-cycle)-free

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 Weighted independent set

Linear from permutation [1164]
Linear from AT-free claw-free [1157]
Polynomial [O(VE)] from (P₅,fork)-free [1125]
Polynomial [O(n^5)] from (K_1,4,P₅)-free [1110]
Polynomial from (K_2,3,P₅)-free [1110]
Polynomial [O(V^5E^3)] from Berge bull-free [1278]
Polynomial from (P₅,cricket)-free [1110]
Polynomial from (P,P₅)-free [1353]
Polynomial [O(n logn logn)] from trapezoid

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

Polynomial from K₂ 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 [O(n^6)] from (K_3,3,P₅)-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 (K_4,4,P₅)-free

Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial from (K_2,3,P,hole)-free [1107]
Polynomial [O(n^2)] from circle [1121]
Polynomial from 4K₁-free
Polynomial from interval filament [1159]
Polynomial [O(n^{6p+2})] from (p,q<=2)-colorable [1116]
Polynomial from (K_1,4,P,P₅,fork)-free [1103]
Polynomial [O(n^4)] from (P₅,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 (P₅,X₈₂,X₈₃)-free [1246]
Polynomial from nearly bipartite
Polynomial [O(VE)] from (bull,fork)-free [1124] [307]
Polynomial from (K_2,3,P,P₅)-free [1107]
Polynomial [O(V^4)] from weakly chordal [997]
Polynomial from subtree overlap [1123]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Linear [O(n)] from circular arc [1105] [1106] [1158]
Linear from co-comparability [1100]
Polynomial from claw-free [947]
Polynomial from co-hereditary clique-Helly [1298]
Polynomial from comparability [453]
Polynomial from (K_3,3-e,P₅)-free [1246]
Polynomial [O(VE)] from (P,P₅)-free [1117]
Polynomial [O(VE)] from weakly chordal [530] [1119]
Polynomial from (E,P)-free [1305]
Polynomial from (K_2,3,P,P₅)-free [1346] [1107]
Polynomial [O(V^8)] from (P,P₇)-free [1351]
Polynomial from (C₆,K_3,3+e,P,P₇,X₃₇,X₄₁)-free [1346]
Polynomial [O(VE)] from (claw,net)-free [1127] [515]
Polynomial from (P,T₂)-free [1305]
Polynomial [O(nm)] from (K_3,3-e,P₅,X₉₈)-free [1117]
Polynomial from (P,star_1,2,5)-free [1349]
Polynomial [O(V^{5})] from (K_3,3-e,P₅,X₉₉)-free [1307]
Polynomial from (P,P₈)-free [1306]
Open from (P,star_1,2,3)-free [1351]
Open from (P,star_1,2,4)-free [1351] [1306]
See also : Weighted independent set

Algorithms for Domination

Linear from circular arc [1143] [1158]
Linear [O(V)] from permutation [1342] [1147] [1148] [1149] [1165]
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]
See also : Cliquewidth expression

Graphclass: (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free