Weakly Perfect Graph

Author

Eric W. Weisstein
May 18, 2017

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

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

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

WeaklyPerfect

All

A198634

1, 2, 4, 11, 33, 152, 1006, 11805, 257542, 11011758, 917095022

Table[Total[Boole[Equal@@@Transpose[Get[FileNameJoin[{$GraphDataDirectory,"Nodes",#,#<>"_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]]&/@{"ChromaticNumber","CliqueNumber"}]]],{n,10}]//Timing

Table[Total[Boole[WeaklyPerfectGraphQ/@Graphs[n]]],{n,8}]//Timing

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

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

Connected

A287009

1, 1, 2, 6, 20, 109, 820, 10618, 244536, 10740858, 905808814

Table[Total[Boole[Equal@@@Transpose[Get[FileNameJoin[{$GraphDataDirectory,"Nodes",#,#<>"_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[ConnectedIndices[[n]]]]&/@{"ChromaticNumber","CliqueNumber"}]]],{n,10}]//Timing

Table[Total[Boole[WeaklyPerfectGraphQ/@ConnectedGraphs[n]]],{n,8}]//Timing

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

Table[Length@GraphData[{"WeaklyPerfect","Connected"},n],{n,7}]

Disconnected

A287023

Agrees with A287008 up to 8 terms

0, 1, 2, 5, 13, 43, 186, 1187, 13006, 270900, 11286208

Table[Total[Boole[Equal@@@Transpose[Get[FileNameJoin[{$GraphDataDirectory,"Nodes",#,#<>"_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[DisconnectedIndices[[n]]]]&/@{"ChromaticNumber","CliqueNumber"}]]],{n,10}]//Timing

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

Take[{1,2,4,11,33,152,1006,11805,257542,11011758},8]-{1,1,2,6,20,109,820,10618}

Cases

GraphData["WeaklyPerfect",;;5]

WeaklyPerfectGraphQ[GraphData["BullGraph"]]

Check

DeleteCases[Monitor[{#,GraphData[#,"WeaklyPerfect"],WeaklyPerfectGraphQ[GraphData[g=#]]}&/@GraphData[;;5],g],{_,x_,x_}]//Timing

DeleteCases[Monitor[{#,GraphData[#,"WeaklyPerfect"],WeaklyPerfectGraphQ[GraphData[g=#]]}&/@GraphData[;;10],g],{_,x_,x_}]//Timing