Perfect Graph

Author

Eric W. Weisstein
February 3, 2024

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/PerfectGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/PerfectGraph.html.

©2024 Wolfram Research, Inc. except for portions noted otherwise

Classes

Classes that are perfect

GraphClassesThatAre["Perfect"]

Perfect graphs are class

Intersection@@(GraphData[#,"Classes"]&/@GraphData["Perfect"])

Counts

Connected

A052433

Table[Total[Boole[PerfectGraphQ/@ConnectedGraphs[n]]],{n,10}]//Timing

Table[Total[Boole[Get["Perfect_"<>If[n<10,"0",""]<>ToString[n]<>".m"][[ConnectedGraphIndices[n]]]]],{n,10}]

Table[Length@GraphData[{"Connected","Perfect"},n],{n,12}]

Disconnected

A286949

A052431={1,2,4,11,33,148,906,8887,136756,3269264,115811998,5855499195};

A052433={1,1,2,6,20,105,724,7805,126777,3122221,112392709,5736233644};

Table[Length@GraphData[{"Disconnected","Perfect"},n],{n,7}]

A052431-A052433

Table[Total[Boole[Get["Perfect_"<>If[n<10,"0",""]<>ToString[n]<>".m"][[DisconnectedIndices[[n]]]]]],{n,10}]

Table[GraphData[#,"Notation"]&/@GraphData[{"Perfect","Disconnected"},n],{n,4}]//Column//TraditionalForm

All

A052431

Table[Total[Boole[PerfectGraphQ/@Graphs[n]]],{n,10}]//Timing

Table[Length@GraphData["Perfect",n],{n,12}]

SetDirectory[FileNameJoin[{$GraphDataDirectory,"Nodes","Perfect"}]]

Table[Total[Boole[Get["Perfect_"<>If[n<10,"0",""]<>ToString[n]<>".m"]]],{n,10}]

Perfect connected nonbipartite

A287511

Table[Total[Boole[(!BipartiteGraphQ[#]&&PerfectGraphQ[#])&/@ConnectedGraphs[n]]],{n,10}]//Timing

Length/@Table[Complement[GraphData[{"Connected","Perfect"},n],GraphData["Bipartite",n]],{n,7}]

Perfect nonbipartite

A287512

Table[Total[Boole[(!BipartiteGraphQ[#]&&PerfectGraphQ[#])&/@Graphs[n]]],{n,10}]//Timing

Length/@Table[Complement[GraphData["Perfect",n],GraphData["Bipartite",n]],{n,7}]

Figures

Simple

GraphicsGrid[Map[Show[StyleGraphs@GraphData[#],PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[14,Italic,FontFamily->"Times",Black]],PageWidth->800/6,TextAlignment->Center]]&,
Flatten[Partition[#,UpTo[6]]&/@DeleteCases[GraphData["Perfect",#]&/@Range[4],{}],1],{2}
],ImageSize->800,Alignment->Top,Dividers->All]

Connected

GraphicsGrid[Map[Show[StyleGraphs@GraphData[#],PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[14,Italic,FontFamily->"Times",Black]],PageWidth->800/6,TextAlignment->Center]]&,
Flatten[Partition[#,UpTo[6]]&/@DeleteCases[GraphData[{"Perfect","Connected"},#]&/@Range[4],{}],1],{2}
],ImageSize->800,Alignment->Top,Dividers->All]

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"Perfect"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"Perfect"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"Perfect"],{n,20}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"Perfect"],{n,20}]

Antiprism

Entity["Graph",{"Antiprism",n}]["Perfect"]

Entity["Graph",{"Antiprism",n}]["Imperfect"]

seq=Table[GraphData[{"Antiprism",n},"Perfect"],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"Perfect"],{n,5}]

Barbell

seq=Table[GraphData[{"Barbell",n},"Perfect"],{n,3,20}]

FindSequenceFunction[seq,n]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"Perfect"],{n,20}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"Perfect"],{n,20}]

Book

seq=Table[GraphData[{"Book",n},"Perfect"],{n,20}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"Perfect"],{n,6}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"Perfect"],{n,20}]

Centipede

seq=Table[GraphData[{"Centipede",n},"Perfect"],{n,10}]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"Perfect"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["Perfect"]

Entity["Graph",{"Complete",n}]["Imperfect"]

seq=Table[GraphData[{"Complete",n},"Perfect"],{n,30}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["Perfect"]

Entity["Graph",{"CompleteBipartite",{m,n}}]["Imperfect"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"Perfect"],
True
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["Perfect"]

Entity["Graph",{"CompleteBipartite",{n,n}}]["Imperfect"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Perfect"],{n,20}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["Perfect"]

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["Imperfect"]

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"Perfect"],
True
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["Perfect"]

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["Imperfect"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"Perfect"],{n,10}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"Perfect"],{n,2,12}]

Crown

seq=Table[GraphData[{"Crown",n},"Perfect"],{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["Perfect"]

Entity["Graph",{"CubeConnectedCycle",n}]["Imperfect"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"Perfect"],{n,3,8}]

Table[Piecewise[{{True,n==3||Mod[n,2]==0}},False],{n,3,8}]==seq

Do[Print[{gn={"CubeConnectedCycle",n},PerfectGraphQ[CubeConnectedCycleGraph[n]]//Timing}],{n,3,10}]

Cycle

Entity["Graph",{"Cycle",n}]["Perfect"]

Entity["Graph",{"Cycle",n}]["Imperfect"]

seq=Table[GraphData[{"Cycle",n},"Perfect"],{n,3,30}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"Perfect"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"Perfect"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"Perfect"],{n,3,20}]

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"Perfect"],{n,0,7}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"Perfect"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["Perfect"]

Entity["Graph",{"Empty",n}]["Imperfect"]

seq=Table[GraphData[{"Empty",n},"Perfect"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"Perfect"],{n,15}]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"Perfect"],{n,20}]

Flower

seq=Table[GraphData[{"Flower",n},"Perfect"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"Perfect"],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"Perfect"],{n,3,20}]

GeneralizedPetersen

SortBy[{GraphData[#,"NotationRules","GeneralizedPetersen"],GraphData[#,"Perfect"]}&/@GraphData["GeneralizedPetersen"],First]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"Perfect"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"Perfect"],{n,3,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["Perfect"]

Entity["Graph",{"Grid",{m,n}}]["Imperfect"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"Perfect"],
True
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["Perfect"]

Entity["Graph",{"Grid",{n,n}}]["Imperfect"]

seq=Table[GraphData[{"Grid",{n,n}},"Perfect"],{n,20}]

FindSequenceFunction[seq,n]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["Perfect"]

Entity["Graph",{"Grid",{k,m,n}}]["Imperfect"]

Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"Perfect"],
True
},{n,5},{m,n},{k,m}],2]

Tally[GraphData[{"Grid",{2,3,4}},"DistanceMatrix"]//Normal//Flatten]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["Perfect"]

Entity["Graph",{"Grid",{n,n,n}}]["Imperfect"]

seq=Table[GraphData[{"Grid",{n,n,n}},"Perfect"],{n,10}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"Perfect"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"Perfect"],{n,5}]

Helm

seq=Table[GraphData[{"Helm",n},"Perfect"],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["Perfect"]

Entity["Graph",{"Hypercube",n}]["Imperfect"]

seq=Table[GraphData[{"Hypercube",n},"Perfect"],{n,0,10}]

Keller

Entity["Graph",{"Keller",n}]["Perfect"]

Entity["Graph",{"Keller",n}]["Imperfect"]

seq=Table[GraphData[{"Keller",n},"Perfect"],{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"Perfect"],{n,20}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["Perfect"]

Entity["Graph",{"Knight",{m,n}}]["Imperfect"]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["Perfect"]

Entity["Graph",{"Knight",{n,n}}]["Imperfect"]

seq=Table[GraphData[{"Knight",{n,n}},"Perfect"],{n,20}]

Ladder

Entity["Graph",{"Ladder",n}]["Perfect"]

Entity["Graph",{"Ladder",n}]["Imperfect"]

seq=Table[GraphData[{"Ladder",n},"Perfect"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"Perfect"],{n,20}]

LucasCube

seq=Table[GraphData[{"LucasCube",n},"Perfect"],{n,15}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"Perfect"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["Perfect"]

Entity["Graph",{"MoebiusLadder",n}]["Imperfect"]

seq=Table[GraphData[{"MoebiusLadder",n},"Perfect"],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["Perfect"]

Entity["Graph",{"Mycielski",n}]["Imperfect"]

seq=Table[GraphData[{"Mycielski",n},"Perfect"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["Perfect"]

Entity["Graph",{"Odd",n}]["Imperfect"]

seq=Table[GraphData[{"Odd",n},"Perfect"],{n,7}]

Pan

seq=Table[GraphData[{"Pan",n},"Perfect"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["Perfect"]

Entity["Graph",{"Path",n}]["Imperfect"]

seq=Table[GraphData[{"Path",n},"Perfect"],{n,20}]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"Perfect"],{n,20}]

Pell

seq=Table[GraphData[{"Pell",n},"Perfect"],{n,9}]

Prism

Entity["Graph",{"Prism",n}]["Perfect"]

Entity["Graph",{"Prism",n}]["Imperfect"]

seq=Table[GraphData[{"Prism",n},"Perfect"],{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"Perfect"],{n,20}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"Perfect"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"Perfect"],{n,20}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"Perfect"],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"Perfect"],{n,5}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"Perfect"],{n,6}]

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"Perfect"],{n,5}]

StackedBook

seq=Table[GraphData[{"StackedBook",{n,n}},"Perfect"],{n,10}]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"Perfect"],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["Perfect"]

Entity["Graph",{"Star",n}]["Imperfect"]

seq=Table[GraphData[{"Star",n},"Perfect"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"Perfect"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"Perfect"],{n,3,20}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"Perfect"],{n,3,20}]

Transposition

Entity["Graph",{"Transposition",n}]["Perfect"]

Entity["Graph",{"Transposition",n}]["Imperfect"]

seq=Table[GraphData[{"Transposition",n},"Perfect"],{n,6}]

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["Perfect"]

Entity["Graph",{"Trapezohedron",n}]["Imperfect"]

seq=Table[GraphData[{"Trapezohedron",n},"Perfect"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"Perfect"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"Perfect"],{n,0,20}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"Perfect"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"Perfect"],{n,20}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"Perfect"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"Perfect"],{n,20}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"Perfect"],{n,20}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"Perfect"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"Perfect"],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["Perfect"]

Entity["Graph",{"Wheel",n}]["Imperfect"]

seq=Table[GraphData[{"Wheel",n},"Perfect"],{n,4,20}]

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"Perfect"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"Perfect"],{n,2,20}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"Perfect"],{n,20}]