ISGCI project home  All classes  Smallgraphs

Graphclass: perfect

Definition:
A graph is perfect if for all induced subgraphs H: \chi(H) = \omega(H), where \chi is the chromatic number and \omega is the size of a maximum clique.

References: [88] [89] [95] [453] [96] [737] [1026]
Equivalent classes:  Berge   cal C(G)-perfect   kernel solvable   (odd anti-hole,odd-hole)-free   perfectly 1-transversable 
Complement classes: self-complementary
Related classes:  2-split cap perfect   K4-free cap perfect   absolutely perfect   bull-free cap perfect   circular perfect   claw-free cap perfect   clique-perfect   diamond-free cap perfect   line cap perfect   locally perfect   minimally imperfect   paw-free cap perfect   perfect cap planar   perfect cap split-neighbourhood   perfect cap triangle-free   strongly perfect   superperfect   trivially perfect   very strongly perfect 

Inclusions

Minimal superclasses:  circular perfect   co-normal   normal   odd anti-hole-free   odd-hole-free 
Maximal subclasses:  (2,0)-colorable   2-split cap perfect   (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   (3K1,C5,K5 - e,co-(C6 cup K1),co-(C7),co-(K3,3 cup K1),co-(K3,3-e cup K1),co-(domino cup K1))-free   (4K1,odd anti-hole,odd-hole)-free   (A,C4 cup 2K1,P2 cup P3,R,co-(K5 - e),co-claw,odd anti-hole,twin-house)-free   Berge cap claw-free   (C5,P6,co-(P6))-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,XF2n+1,XF3n,XF4n,co-XF12n+3,co-XF52n+3,co-XF62n+2,odd anti-hole)-free   Dilworth 4   Gallai-perfect   (P5,bull,odd anti-hole)-free   PI*   (W4,claw,gem,odd-hole)-free   (X12,X5,X95,X96,X97,co-(X12),co-(X5),co-(X95),co-(X96),co-(X97),co-(claw cup triangle),claw cup triangle,co-cricket,co-twin-house,cricket,odd anti-hole,odd-hole,twin-house)-free   (co-(W4),co-claw,co-gem,odd anti-hole)-free   absorbantly perfect   alternately colourable   biclique separable   bip*   bipartite cup co-bipartite cup co-line graphs of bipartite graphs cup line graphs of bipartite graphs   (claw,odd anti-hole,odd-hole)-free   claw-free cap perfect   co-biclique separable   co-bipartite   (co-claw,co-diamond,odd anti-hole)-free   (co-claw,odd anti-hole,odd-hole)-free   co-comparability   (co-diamond,odd anti-hole)-free   co-line graphs of bipartite graphs   (co-paw,odd anti-hole)-free   co-probe cograph   (diamond,odd-hole)-free   diamond-free cap perfect   line graphs of bipartite multigraphs   locally perfect   multitolerance   murky   neighbourhood perfect   odd anti-cycle-free   (odd-hole,paw)-free   odd-hole-free cap planar   odd-hole-free cap pretty   paw-free cap perfect   perfect cap planar   perfect cap split-neighbourhood   preperfect   probe Meyniel   probe chordal   quasi-parity   short-chorded   slender   slightly triangulated   slim   superperfect   totally unimodular   tree-perfect   unimodular 

Problems summary

Recognition:Polynomialdetails
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth:Unboundeddetails
Weighted independent set:Polynomialdetails
Independent set:Polynomialdetails
Domination:NP-completedetails

Algorithms for Recognition

Polynomial [1226] [1227] [1228]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth


Unbounded from bipartite permutation  [1182]
Unbounded from (2K2,co-(C6),odd anti-cycle)-free 
     From the complement .



Unbounded from co-comparability graphs of posets of interval dimension 2, height 1 
     See  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 
     From the complement .



Unbounded from unit interval  [1177]


Unbounded from co-P4-brittle 
     See  P4-brittle 


Unbounded from split  [1176]
Unbounded from (S3,co-(Cn+4),co-claw,net)-free 
     From the complement .



Unbounded from co-Welsh-Powell perfect 
     See  Welsh-Powell perfect  .



Unbounded from (co-(Cn+4),co-claw)-free 
     From the complement .

Unbounded from (S3,co-(Cn+4),co-claw)-free 
     From the complement .





Unbounded from C4-free cap C6-free cap bipartite  [1183]



Unbounded from (P5,S3,co-(A),co-(E),co-(X1),anti-hole,co-domino,co-rising sun,net)-free 
     From the complement .



Unbounded from co-bipartite 
     See  bipartite  .

Unbounded from grid  [1177]

Unbounded from chordal  [1174]

Unbounded from (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free 
     From the complement .





Unbounded from (S3,co-(Cn+4),co-(S3 cup K1),co-claw)-free 
     From the complement .






Unbounded from (co-(Cn+4),co-(H))-free 
     From the complement .


Unbounded from (C5,P,P5,co-(P),house)-free  [1185]

Unbounded from co-interval 
     See  interval  .


See also : Cliquewidth expression

Algorithms for Weighted independent set

Polynomial [476]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

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 bipartite  [1142]
NP-complete from partial grid  [1162] [630]
NP-complete from comparability  [1142]
NP-complete from split  [1144] [1145]
See also : Cliquewidth expression