k-Chromatic Graph

Author

Eric W. Weisstein
June 2, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/k-ChromaticGraph.nb.

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

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

Enumeration

n=7

v4.2

chromatic=Table[ChromaticNumber/@Graphs[n],{n,7}];//Timing

v5.0

<<Graphs`;
chromatic=Table[ChromaticNumber/@Graphs[n],{n,7}];//Timing

n=8

v4.2

chromatic=Table[ChromaticNumber/@Graphs[n],{n,8}];//Timing

v5.0

<<Graphs`;
chromatic=Table[ChromaticNumber/@Graphs[n],{n,8}];//Timing

n=9

v4.2

chromatic=Table[ChromaticNumber/@Graphs[n],{n,9}];//Timing

v5.0

<<Graphs`;
chromatic=Table[ChromaticNumber/@Graphs[n],{n,9}];//Timing

Simple

Counts

chromatic

chromaticcounts=Map[Length,Split/@Sort/@chromatic,{2}]

Transpose[PadRight[#,Length[Last[chromaticcounts]]]&/@chromaticcounts]

Table[Count[#,n]&/@chromatic,{n,9}]//ColumnForm

2-Colorable

Off[General::"stop"]

ShowGraphArray[Flatten[Partition[#,8,8,{1,1},{}]&/@Map[MinimalColoring[RecognizeGraph[#],Colors->{Red,Blue}]&,Table[Graphs[n][[Flatten[Position[chromatic[[n]],2]]]],{n,5}],{2}],
1],
VertexColor->Red,
VertexStyle->Disk[.15],
AspectRatio->1,
PlotRange->All,
GraphicsSpacing->.5]

3-Colorable

ShowGraphArray[Flatten[Partition[#,8,8,{1,1},{}]&/@Map[MinimalColoring[RecognizeGraph[#],Colors->{Red,Green,Blue}]&,Table[Graphs[n][[Flatten[Position[chromatic[[n]],3]]]],{n,5}],{2}],
1],
VertexColor->Red,
VertexStyle->Disk[.15],
AspectRatio->1,
PlotRange->All,
GraphicsSpacing->.5]

4-Colorable

ShowGraphArray[Flatten[Partition[#,8,8,{1,1},{}]&/@Map[MinimalColoring[RecognizeGraph[#],Colors->{Red,Green,Blue,Black}]&,Table[Graphs[n][[Flatten[Position[chromatic[[n]],4]]]],{n,5}],{2}],
1],
VertexColor->Red,
VertexStyle->Disk[.15],
AspectRatio->1,
PlotRange->All,
GraphicsSpacing->.5]

Simple Connected

Counts

connected=Flatten[Position[#,_?ConnectedQ,{1}]]&/@Graphs/@Range[8];

connectedchromatic=MapIndexed[chromatic[[#2[[1]]]][[#1]]&,connected];

connectedchromaticcounts=Map[Length,Split/@Sort/@connectedchromatic,{2}]

connectedchromaticcounts=Prepend[Prepend[#,0]&/@Rest[Map[Length,Split/@Sort/@connectedchromatic,{2}]],{1}]

Transpose[PadRight[#,Length[Last[connectedchromaticcounts]]]&/@connectedchromaticcounts]

(connected=Table[Count[Graphs[n][[Flatten[Position[chromatic[[n]],c]]]],_?ConnectedQ],{c,9},{n,9}])//ColumnForm

2-Chromatic

ShowGraphArray[Flatten[Partition[#,8,8,{1,1},{}]&/@Map[MinimalColoring[RecognizeGraph[#],Colors->{Red,Blue}]&,Table[Select[Graphs[n][[Flatten[Position[chromatic[[n]],2]]]],ConnectedQ],{n,5}],{2}],
1],
VertexColor->Red,
VertexStyle->Disk[.15],
AspectRatio->1,
GraphicsSpacing->.5]

3-Chromatic

Sequences of numbers of graphs on 1, 2, 3, … nodes that are 1-colorable, 2-colorable, etc.

ShowGraphArray[Flatten[Partition[#,8,8,{1,1},{}]&/@Map[MinimalColoring[RecognizeGraph[#],Colors->{Red,Green,Blue}]&,Table[Select[Graphs[n][[Flatten[Position[chromatic[[n]],3]]]],ConnectedQ],{n,5}],{2}],
1],
VertexColor->Red,
VertexStyle->Disk[.15],
AspectRatio->1,
GraphicsSpacing->.5]

4-Chromatic

ShowGraphArray[Flatten[Partition[#,8,8,{1,1},{}]&/@Map[MinimalColoring[RecognizeGraph[#],Colors->{Red,Green,Blue,Black}]&,Table[Select[Graphs[n][[Flatten[Position[chromatic[[n]],4]]]],ConnectedQ],{n,5}],{2}],
1],
VertexColor->Red,
VertexStyle->Disk[.15],
AspectRatio->1,
GraphicsSpacing->.5]

Labeled

Counts

labeledchromatic=Table[ChromaticNumber/@LabeledGraphs[n],{n,6}];//Timing

labeledchromaticcounts=Map[Length,Split/@Sort/@labeledchromatic,{2}]

l=Transpose[PadRight[#,Length[Last[labeledchromaticcounts]]]&/@labeledchromaticcounts]

2-Chromatic

ShowGraphArray[Flatten[Partition[#,10,10,{1,1},{}]&/@Map[MinimalColoring[#,Colors->{Red,Blue}]&,Table[LabeledGraphs[n][[Flatten[Position[labeledchromatic[[n]],2]]]],{n,4}],{2}],
1],
VertexColor->Red,VertexStyle->Disk[.2],
AspectRatio->1,PlotRange->All,
VertexLabel->Range[5],VertexLabelPosition->{-.1,.3},
GraphicsSpacing->.5]

3-Chromatic

ShowGraphArray[Flatten[Partition[#,10,10,{1,1},{}]&/@Map[MinimalColoring[#,Colors->{Red,Blue,Green}]&,Table[LabeledGraphs[n][[Flatten[Position[labeledchromatic[[n]],3]]]],{n,4}],{2}],
1],
VertexColor->Red,VertexStyle->Disk[.2],
AspectRatio->1,PlotRange->All,
VertexLabel->Range[5],VertexLabelPosition->{-.1,.3},
GraphicsSpacing->.5]

Labeled Connected

Counts

labeledconnected=Flatten[Position[#,_?ConnectedQ,{1}]]&/@LabeledGraphs/@Range[6];//Timing

labeledconnectedchromatic=MapIndexed[labeledchromatic[[#2[[1]]]][[#1]]&,labeledconnected];

labeledconnectedchromaticcounts=Prepend[Prepend[#,0]&/@Rest[Map[Length,Split/@Sort/@labeledconnectedchromatic,{2}]],{1}]

lc=Transpose[PadRight[#,Length[Last[labeledconnectedchromaticcounts]]]&/@labeledconnectedchromaticcounts]

2-Chromatic

ShowGraphArray[Flatten[Partition[#,10,10,{1,1},{}]&/@Map[MinimalColoring[#,Colors->{Red,Blue}]&,Table[Select[LabeledGraphs[n][[Flatten[Position[labeledchromatic[[n]],2]]]],ConnectedQ],{n,4}],{2}],
1],
VertexColor->Red,VertexStyle->Disk[.2],
AspectRatio->1,PlotRange->All,
VertexLabel->Range[5],VertexLabelPosition->{-.1,.3},
GraphicsSpacing->.5]

3-Chromatic

ShowGraphArray[Flatten[Partition[#,10,10,{1,1},{}]&/@Map[MinimalColoring[#,Colors->{Red,Blue,Green}]&,Table[Select[LabeledGraphs[n][[Flatten[Position[labeledchromatic[[n]],3]]]],ConnectedQ],{n,4}],{2}],
1],
VertexColor->Red,VertexStyle->Disk[.2],
AspectRatio->1,PlotRange->All,
VertexLabel->Range[5],VertexLabelPosition->{-.1,.3},
GraphicsSpacing->.5]