ISGCI project home All classes SmallgraphsGraphclass: weakly chordal
Definition:
A graph is weakly chordal
if it is
(anti-hole,hole)-free
.
References:
[526]
Equivalent classes:
(anti-hole,hole)-free
Complement classes:
self-complementary
Related classes:
(P5,co-(C6))-free 
weakly chordal bipartite weakly chordal chordal comparability weakly chordal house-free weakly chordal probe chordal weakly chordal sun-free weakly chordal
Inclusions
Minimal superclasses:
(6,1)-even-chordal (C6,co-(C6))-free bip* even anti-hole-free even-hole-free hole-free perfectly contractile
Maximal subclasses:
(1,2)-polar 2-leaf power 2-threshold (2K3 + e,C5,C6,P6,X5,co-(2P4),co-(A),co-(C6),co-(C7),co-(E),co-(P7),co-(R),co-(X1),co-(X103),co-(X5),co-(X58),co-(X84),co-(X98),antenna,co-domino,co-rising sun,co-twin-house,domino,parachute,parapluie,rising sun,sunlet4)-free (2K3,2P3,C5,C6,C7,K2,3,K3 
P3,X84,co-(3K2),co-(C4 P2),co-(C6),co-(P2 P4),co-(P6),co-(X18),co-(X5),co-antenna,co-domino,co-fish)-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-(T2),co-(X2),co-(X3),anti-hole)-free (3K2,C4 P2,C5,C6,K2 K3,K3,3,K3,3+e,P2 P4,P6,X18,X5,co-(2P3),co-(C6),co-(C7),co-(X84),antenna,domino,fish)-free (8,4) (C5,C6,P6,X17,X18,X5,X98,co-(C6),co-(P6),antenna,domino)-free (C5,C6,P6,co-(C6),co-(P6),co-(X17),co-(X18),co-(X5),co-(X98),co-antenna,co-domino)-free (C5,C6,P6,co-(C6),co-(P6))-free (C5,P5,co-(C6),co-(C7),co-(C8),co-(P8),co-(X19),co-(X20),co-(X21),co-(X22),co-gem)-free (C5,P5,house)-free C5-free P4-tidy (C6,P6,co-(P6),co-(X10),co-(X11),co-(X12),co-(X13),co-(X14),co-(X15),co-(X5),co-(X6),co-(X7),co-(X8),co-(X9),anti-hole,co-antenna)-free (C6,co-(C6))-free murky (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X36,XF12n+3,XF2n+1,XF3n,XF4n,XF52n+3,XF62n+2,co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X36),co-XF12n+3,co-XF2n+1,co-XF3n,co-XF4n,co-XF52n+3,co-XF62n+2,odd anti-hole)-free (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X36,XF12n+3,XF2n+1,XF3n,XF4n,XF52n+3,XF62n+2,co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X36),co-XF12n+3,co-XF2n+1,co-XF3n,co-XF4n,co-XF52n+3,co-XF62n+2,odd-hole)-free HHD-free co-HHD-free HHDA-free Meyniel co-Meyniel P3-free P4-lite P4-simplicial (P5,S3,co-(A),co-(E),co-(X1),anti-hole,co-domino,co-rising sun,net)-free (P5,co-(A),co-(P6),anti clique wheel,anti-hole,co-domino)-free (P5,co-(A),anti-hole,co-domino)-free (P5,co-(P),anti-hole)-free (P5,anti-hole,co-bicycle,co-domino)-free (P5,anti-hole,co-domino,co-gem)-free (P5,anti-hole,co-domino,co-sun)-free (P5,anti-hole,co-domino)-free (P5,anti-hole,co-gem)-free (P6,X10,X11,X12,X13,X14,X15,X5,X6,X7,X8,X9,co-(C6),co-(P6),antenna,hole)-free PI (T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,XF2n+1,XF3n,XF4n,anti-hole,co-XF12n+3,co-XF52n+3,co-XF62n+2,hole)-free Welsh-Powell opposition (XC7,co-(XC1),co-(XC2),co-(XC3),co-(XC4),co-(XC5),co-(XC6),co-(XC8))-free (co-(2C4),co-(3K2),co-(C6),co-(E),co-(P2 P4),co-(P6),co-(X25),co-(X26),co-(X27),co-(X28),co-(X29),odd anti-cycle)-free co-(Cn+4)-free (co-(T3),co-(X81),co-cycle)-free absolutely perfect (anti-hole,co-domino,odd anti-cycle)-free (anti-hole,co-sun,hole)-free (anti-hole,hole,sun)-free (anti-hole,odd anti-cycle)-free bipartite convex-round bithreshold bounded multitolerance charming chordal-perfect circle graph with equator co-HHD-free co-charming co-chordal co-comparability comparability co-comparability graphs of posets of interval dimension 2 co-cycle-free co-forest-perfect co-permutation co-tolerance cograph contraction comparability graphs of dimension 2 posets containment graph of intervals convex domination even-hole-free probe chordal forest-perfect generalized strongly chordal good hereditary V-perfect hereditary Welsh-Powell perfect interval bigraph permutation probe chordal weakly chordal probe cograph quasitriangulated split-perfect strongly orderable sun-free weakly chordal tolerance trapezoid unit tolerance weak bipolarizable
Problems summary
| Recognition: | Polynomial | details |
| Cliquewidth expression: |
Unbounded or NP-complete
| details |
| Cliquewidth: | Unbounded | details |
| Weighted independent set: | Polynomial | details |
| Independent set: | Polynomial | details |
| Domination: | NP-complete | details |
Algorithms for Recognition
Polynomial [O(V^4)]
[997]
[530]
Algorithms for Cliquewidth expression
See also
: Cliquewidth : Weighted independent set : Domination
Algorithms for Cliquewidth
Unbounded from bipartite permutation
[1182]
Unbounded from co-comparability graphs of posets of interval dimension 2, height 1
Unbounded from permutation
[1177]
Unbounded from (co-(Cn+4),co-XF2n+1,co-XF3n,co-claw)-free
Unbounded from unit interval
[1177]
Unbounded from split
[1176]
Unbounded from (S3,co-(Cn+4),co-claw,net)-free
Unbounded from (co-(Cn+4),co-claw)-free
Unbounded from (S3,co-(Cn+4),co-claw)-free
Unbounded from (P5,S3,co-(A),co-(E),co-(X1),anti-hole,co-domino,co-rising sun,net)-free
Unbounded from chordal
[1174]
Unbounded from (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free
Unbounded from (S3,co-(Cn+4),co-(S3 K1),co-claw)-free
Unbounded from (co-(Cn+4),co-(H))-free
Unbounded from (C5,P,P5,co-(P),house)-free
[1185]
Unbounded from co-interval
See also
: Cliquewidth expression Algorithms for Weighted independent set
Polynomial from perfect
[476]
Polynomial [O(V^4)]
[997]
See also
: Cliquewidth expression : Independent set
Algorithms for Independent set
Polynomial [O(VE)]
[530]
[1119]
See also
: Weighted independent set
Algorithms for Domination
NP-complete from chordal
[1146]
NP-complete from chordal bipartite
[1156]
NP-complete from undirected path
[1146]
NP-complete from co-trapezoid
[1172]
NP-complete from split
[1144]
[1145]
See also
: Cliquewidth expression