Chromatic Number

Author

Eric W. Weisstein
January 19, 2024

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

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

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

Counts

All

A084268

(cnts=Sort[Tally[MyChromaticNumber/@Graphs[#]]]&/@Range[7])//Column

(cnts=Tally[Sort[Get[#]]][[All,2]]&/@FileNames["*.m","/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes/ChromaticNumber"])//Column

Length[cnts]

Flatten[cnts]

SetDirectory["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes/ChromaticNumber"]

Do[
Print[{n,Length[a[n]=Get["ChromaticNumber_"<>If[n>9,"","0"]<>ToString[n]<>".m"]]//Timing}],
{n,10}]

Mean

Mean/@Array[a,10]

N[%]

ListPlot[%]

Total

A348620

Total/@Array[a,10]

ListLogPlot[%]

Connected

A084269

Flatten[connected=Table[With[{t=Tally[Sort[GraphData[#,"ChromaticNumber"]&/@GraphData["Connected",n]]]},If[FreeQ[t,{1,_}],Prepend[t,{1,0}],t]][[All,-1]],{n,7}]]

connected//Column

Flatten[connected=Table[With[{t=Tally[Sort[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","ChromaticNumber","ChromaticNumber_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[ConnectedGraphIndices[n]]]]]},If[FreeQ[t,{1,_}],Prepend[t,{1,0}],t]][[All,-1]],{n,10}]]

connected//Column

Figures

Show[GraphicsArray[
Block[{$DisplayFunction=Identity},Partition[ShowGraph[MinimalColoring[#],
VertexStyle->Disk[.08],AspectRatio->Automatic,PlotLabel->TraditionalForm[γ[GraphNotation[#]]==ChromaticNumber[#]]]&/@{CompleteGraph[6],Cycle[5],Cycle[6],Star[6],Wheel[5],Wheel[6]},
3]
]
],ImageSize->500
]

Interpolating polynomial

Cubical graph (Subscript[Q, 3])

GraphData["Q3","ChromaticNumber"]

GraphData["Q3","ChromaticPolynomial"][x]//Expand

cols={0,2,114,2652,29660,198030,932862,3440024};

pts=MapIndexed[{#2[[1]]-1,#}&,Prepend[cols,0]]

InterpolatingPolynomial[pts,x]//Expand

Plot[-133 x+423 (x^2)-572 (x^3)+441 (x^4)-214 (x^5)+66 (x^6)-12 (x^7)+(x^8),{x,0,3}]

Table[%,{x,8}]

P[y_,j_,z_]:=y[[j]] Times@@(((z-#)/(j-#))&/@DeleteCases[Range[Length[y]],j])

Total[P[cols,#,z]&/@Range[Length[cols]]]//Simplify

Relationships

CliqueCoveringNumber of GraphComplement

DeleteCases[{#,VertexChromaticNumber[GraphData[#]],CliqueCoveringNumber[GraphComplement[GraphData[#]]]}&/@GraphData[;;8],{_,x_,x_}]//Timing

Parametrized families

GraphDataCountTable["ChromaticNumber",{"PathComplement"->004526,"Queen"->088202}]

Andrasfai

Table[GraphData[{"Andrasfai",n},"ChromaticNumber"],{n,10}]

Antiprism

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

Table[GraphData[{"Antiprism",n},"ChromaticNumber"],{n,3,25}]

Apollonian

Table[GraphData[{"Apollonian",n},"ChromaticNumber"],{n,6}]

Barbell

Table[GraphData[{"Barbell",n},"ChromaticNumber"],{n,3,20}]

Bishop n×n

Table[GraphData[{"Bishop",{n,n}},"ChromaticNumber"],{n,10}]

BlackBishop n×n

Table[GraphData[{"BlackBishop",{n,n}},"ChromaticNumber"],{n,10}]

Book

Table[GraphData[{"Book",n},"ChromaticNumber"],{n,20}]

Centipede

Table[GraphData[{"Centipede",n},"ChromaticNumber"],{n,10}]

CocktailParty

Table[GraphData[{"CocktailParty",n},"ChromaticNumber"],{n,20}]

CompleteBipartite m×n

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

CompleteBipartite n×n

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

Table[GraphData[{"CompleteBipartite",{n,n}},"ChromaticNumber"],{n,20}]

Complete

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

Table[GraphData[{"Complete",n},"ChromaticNumber"],{n,20}]

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

Table[GraphData[{"CompleteTripartite",{n,n,n}},"ChromaticNumber"],{n,10}]

CrossedPrism

Table[GraphData[{"CrossedPrism",2n},"ChromaticNumber"],{n,2,10}]

Crown

Table[GraphData[{"Crown",n},"ChromaticNumber"],{n,3,20}]

CubeConnectedCycle

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

Table[GraphData[{"CubeConnectedCycle",n},"ChromaticNumber"],{n,3,8}]

Cycle

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

Table[GraphData[{"Cycle",n},"ChromaticNumber"],{n,3,20}]

DiagonalIntersection

A320604

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

FindLinearRecurrence[seq]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

gf=(x^3)FindGeneratingFunction[seq,x]//Factor

gf//InputForm

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>2&&n∈Integers]

CoefficientList[Series[-(((3+3 x+4 (x^2)+3 (x^3)+4 (x^4)+3 (x^5)))/((-1+x) (1+x) (1-x+(x^2)) (1+x+(x^2)))),{x,0,20}],x]

seq=Table[(1/3) (10-(((-1))^n)+Cos[((n π)/3)]-Cos[((2 n π)/3)]),{n,100}]

FindLinearRecurrence[seq]

LinearRecurrence[{0,0,0,0,0,1},{4,3,3,3,4,3},20]

Table[Piecewise[{{4,Mod[n,6]==1||Mod[n,6]==5}},3],{n,20}]

Empty

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

Table[GraphData[{"Empty",n},"ChromaticNumber"],{n,30}]

FibonacciCube

Table[GraphData[{"FibonacciCube",n},"ChromaticNumber"],{n,15}]

FoldedCube

Table[GraphData[{"FoldedCube",n},"ChromaticNumber"],{n,2,10}]

Gear

Table[GraphData[{"Gear",n},"ChromaticNumber"],{n,3,20}]

Grid m×n

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

grids=Select[GraphData["Grid"],Head@FirstCase[GraphData[#,"StandardNames"],{"Grid",{_,_}}]=!=Missing&]

DeleteCases[{#,FirstCase[GraphData[#,"StandardNames"],{"Grid",i:{_,_}}:>i],GraphData[#,"ChromaticNumber"]}&/@grids,{_,_,2}]

Grid n×n

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

Table[GraphData[{"Grid",{n,n}},"ChromaticNumber"],{n,10}]

Grid k×m×n

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

grids=Select[GraphData["Grid"],Head@FirstCase[GraphData[#,"StandardNames"],{"Grid",{_,_,_}}]=!=Missing&]

DeleteCases[{#,FirstCase[GraphData[#,"StandardNames"],{"Grid",i:{_,_,_}}:>i],GraphData[#,"ChromaticNumber"]}&/@grids,{_,_,2}]

Grid n×n×n

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

Table[GraphData[{"Grid",{n,n,n}},"ChromaticNumber"],{n,10}]

HalvedCube

First 8 terms match A06238 but 9th term is <= 14

Pratt hasn't been able to find these either

Table[GraphData[{"HalvedCube",n},"ChromaticNumber"],{n,10}]

Table[VertexChromaticNumber[GraphData[{"HalvedCube",n}]],{n,10}]//Timing

bug(342762): Add nice Possible Issue example for FindLinearRecurrence

seq=2^Floor[Log2[Range[0,50]]+1];

DeleteCases[Table[{n,FindLinearRecurrence[Take[seq,n]]},{n,Length[seq]}],{_,_FindLinearRecurrence}]//Column

Hanoi

Table[GraphData[{"Hanoi",n},"ChromaticNumber"],{n,5}]

Helm

Table[GraphData[{"Helm",n},"ChromaticNumber"],{n,3,20}]

Hypercube

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

Table[GraphData[{"Hypercube",n},"ChromaticNumber"],{n,0,10}]

Keller

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

A151821

Table[GraphData[{"Keller",n},"ChromaticNumber"],{n,5}]

King n×n

Table[GraphData[{"King",{n,n}},"ChromaticNumber"],{n,10}]

Knight m×n

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

Knight n×n

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

Table[GraphData[{"Knight",{n,n}},"ChromaticNumber"],{n,20}]

Ladder

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

Table[GraphData[{"Ladder",n},"ChromaticNumber"],{n,20}]

LadderRung

Table[GraphData[{"LadderRung",n},"ChromaticNumber"],{n,20}]

MengerSponge

Table[GraphData[{"MengerSponge",n},"ChromaticNumber"],{n,3}]

MoebiusLadder

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

Table[GraphData[{"MoebiusLadder",n},"ChromaticNumber"],{n,3,25}]

Mycielski

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

Table[GraphData[{"Mycielski",n},"ChromaticNumber"],{n,11}]

Odd

Table[GraphData[{"Odd",n},"ChromaticNumber"],{n,7}]

Pan

Table[GraphData[{"Pan",n},"ChromaticNumber"],{n,3,20}]

Path

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

Table[GraphData[{"Path",n},"ChromaticNumber"],{n,20}]

PermutationStar

Table[GraphData[{"PermutationStar",n},"ChromaticNumber"],{n,6}]

Prism

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

Table[GraphData[{"Prism",n},"ChromaticNumber"],{n,3,25}]

Queen n×n

A088202

a(27) is the first open case.

Table[GraphData[{"Queen",{n,n}},"ChromaticNumber"],{n,20}]

Correct:

col=GraphData[{"Queen",{8,8}},"MinimumVertexColoring"]

VertexColoringQ[GraphData[{"Queen",{8,8}}],col]

bug(414915): VertexChromaticNumber, FindVertexColoring return incorrect results

$Version

Incorrect:

VertexChromaticNumber[GraphData[{"Queen",{8,8}}]]

FindVertexColoring[GraphData[{"Queen",{8,8}}]]

Max[%]

Wrong for n>7

Do[Print[{n,VertexChromaticNumber[QueenGraph[n,n]]//Timing}],{n,10}]

Rook n×n

Table[GraphData[{"Rook",{n,n}},"ChromaticNumber"],{n,10}]

RookComplement n×n

Table[GraphData[{"RookComplement",{n,n}},"ChromaticNumber"],{n,10}]

SierpinskiCarpet

Table[GraphData[{"SierpinskiCarpet",n},"ChromaticNumber"],{n,4}]

SierpinskiSieve

Table[GraphData[{"SierpinskiSieve",n},"ChromaticNumber"],{n,5}]

SierpinskiTetrahedron

Table[GraphData[{"SierpinskiTetrahedron",n},"ChromaticNumber"],{n,6}]

Star

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

Table[GraphData[{"Star",n},"ChromaticNumber"],{n,20}]

Sun

Table[GraphData[{"Sun",n},"ChromaticNumber"],{n,3,20}]

Sunlet

Table[GraphData[{"Sunlet",n},"ChromaticNumber"],{n,3,20}]

Tetrahedral

Possibly A011978?

Table[GraphData[{"Tetrahedral",n},"ChromaticNumber"],{n,6,10}]

TorusGrid n×n

Table[GraphData[{"TorusGrid",{n,n}},"ChromaticNumber"],{n,3,10}]

Transposition

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

Table[GraphData[{"Transposition",n},"ChromaticNumber"],{n,6}]

Triangular

A109613

Table[GraphData[{"Triangular",n},"ChromaticNumber"],{n,2,20}]

TriangularGrid

Table[GraphData[{"TriangularGrid",n},"ChromaticNumber"],{n,10}]

TriangularHoneycombAcuteKnight

Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"ChromaticNumber"],{n,20}]

TriangularHoneycombObtuseKnight

Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"ChromaticNumber"],{n,20}]

TriangularHoneycombQueen

Add to OEIS

Table[GraphData[{"TriangularHoneycombQueen",n},"ChromaticNumber"],{n,10}]

TriangularHoneycombRook

Table[GraphData[{"TriangularHoneycombRook",n},"ChromaticNumber"],{n,10}]

Web

Table[GraphData[{"Web",n},"ChromaticNumber"],{n,3,20}]

Wheel

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

Table[GraphData[{"Wheel",n},"ChromaticNumber"],{n,4,20}]

WhiteBishop n×n

A052928

Table[GraphData[{"WhiteBishop",{n,n}},"ChromaticNumber"],{n,2,10}]

Algorithms

Built-in

FindVertexColoring[GraphData[{"Rook", {6, 7}}], PerformanceGoal -> "Quality"] (and others) incorrectly return non-minimal colorings

Brooks' theorem (doesn't apply since much better colorings are found)

bug(415898): FindVertexColoring[GraphData[{"Rook", {6, 7}}], PerformanceGoal -> "Quality"] (and others) incorrectly return non-minimal colorings

$Version

data=Monitor[{g=#,GraphData[#,"ChromaticNumber"],VertexChromaticNumber[GraphData[#],PerformanceGoal->"Quality"]//Timing}&/@GraphData[All],g];//Timing

bad=DeleteCases[data,{_,x_,{_,x_}}|{_,_Missing,_}]

TextGrid[{#,#2,#3[[2]],#3[[2]]-#2}&@@@bad,Dividers->All,Alignment->{{Left,{Decimal}}}]

Unknown

data=Monitor[{
g=#,
GraphData[#,"MaximalIndependentVertexSetCount"],
GraphData[#,"V"],
VertexChromaticNumber[GraphData[#],PerformanceGoal->"Quality"]}&/@Select[GraphData[All],MissingQ[GraphData[#,"ChromaticNumber"]]&],g];//Timing

TextGrid[SortBy[data,Last],Dividers->All,Alignment->{{Left,{Decimal}}}]

Empty graphs

VertexChromaticNumber[Graph[{}]]

FindVertexColoring[Graph[{}]]

data=Monitor[{g=#,GraphData[#,"ChromaticNumber"],VertexChromaticNumber[GraphData[#],PerformanceGoal->"Quality"]//Timing}&/@GraphData["Empty"],g];//Timing

data

VertexChromaticNumber[bipartite graph] could return 2 more quickly

$Version

data=Monitor[{g=#,GraphData[#,"ChromaticNumber"],VertexChromaticNumber[GraphData[#],PerformanceGoal->"Quality"]//Timing}&/@GraphData[{"Bipartite","Nonempty"}],g];//Timing

DeleteCases[data,{_,x_,{_,x_}}]

Reverse@SortBy[data,#[[3,1]]&]

BipartiteGraphQ[GraphData[{"Cage",{14,8}}]]//RepeatedTiming

Trick+Wagon

https://resources.wolframcloud.com/FunctionRepository/resources/ChromaticNumber

ChromaticNumberWagon[G_Graph] := Max @ VertexColoringSWStatic[G];

VertexColoringSWStatic[g_ /; ConnectedGraphQ[g]] := Module[
	{i, sol, inds, S},
	sol = ISByILPInteger[S = MaximalIndependentSets @ g];
	inds = Part[S,
		Cases[sol[[2]],
			HoldPattern[Rule[Pattern[r, _][z_], 1]] :> z
		]
	];
	Table[Part[Position[inds, i], 1, 1], {i, VertexCount @ g}]
];

VertexColoringSWStatic[g_ /; !ConnectedGraphQ[g]] := Module[
	{comps = Map[Sort, ConnectedComponents @ g]},
	Map[Last,
		Sort @ Transpose @ Map[Flatten,
			{
				comps,
				Table[VertexColoringSWStatic @ IndexGraph @ Subgraph[g, c],
					{c, comps}
				]
			}
		]
	]
];

ISByILPInteger[S_] := Module[
	{n = Length @ S, v, obj, con0, con1, sol, verts, x},
	v = Map[x, Range @ n];
	obj = Total @ v;
	verts = Union @@ S;
	con0 = {Thread @ LessEqual[0, v, 1], Element[v, Integers]};
	con1Left = Table[
		Total[
			Map[x,
				Select[Range @ n, Function[MemberQ[Part[S, #], j]]]
			]
		],
		{j, verts}
	];
	con1 = Thread @ GreaterEqual[con1Left, 1];
	NMinimize[{obj, Flatten @ {con0, con1}}, v]
];

MaximalIndependentSets[g1_] := Module[
	{rr, count, g = GraphComplement @ g1, P, adj},
	adj = ToAdjacencyListsBasic @ g;
	BronKerbosch1[R_, {}, {}] := Sow @ R;
	BronKerbosch1[R_, P_, X_] := Module[{X1 = X, P1 = P, v, u},
		u = If[Unequal[P, {}], P[[1]], X[[1]]];
		Do[
			BronKerbosch1[Append[R, v],
				Intersection[P1, adj[[v]]],
				Intersection[X1, adj[[v]]]
			];
			P1 = DeleteCases[P1, v, 1, 1];
			AppendTo[X1, v],
			{v, Complement[P, adj[[u]]]}
		]
	];
	rr = Part[Reap @ BronKerbosch1[{}, Range @ VertexCount @ g, {}], 2, 1];
	Return[rr]
];

ToAdjacencyListsBasic[g_Graph] := Module[
	{s, e = List@@@EdgeList[g]},
	s = Join[e,
		Map[Reverse, e],
		Map[{#, -1}&, Range @ VertexCount @ g]
	];
	Map[Rest, Part[SplitBy[Sort @ s, First], All, All, 2]]
];

adj$2315307 = {{}, {}, {}, {}};
Attributes[adj$2315307] := {Temporary};
BronKerbosch1[R_, {}, {}] := Sow @ R;
BronKerbosch1[R$_, P$_, X$_] := Module[
	{X1$ = X$, P1$ = P$, v$, u$},
	u$ = If[Unequal[P$, {}], P$[[1]], X$[[1]]];
	Do[
		BronKerbosch1[Append[R$, v$],
			Intersection[P1$, adj$2315307[[v$]]],
			Intersection[X1$, adj$2315307[[v$]]]
		];
		P1$ = DeleteCases[P1$, v$, 1, 1];
		AppendTo[X1$, v$],
		{v$, Complement[P$, adj$2315307[[u$]]]}
	]
];

ColoringGreedy[g_] := Module[{g1},
	g1 = g;
	Part[
		Reap[
			While[Unequal[VertexList @ g1, {}],
				is = MaximalIndependentSet @ g1;
				Sow @ is;
				g1 = Subgraph[g1, Complement[VertexList @ g1, is]]
			]
		],
		2, 1
	]
];

MaximalIndependentSet[g_] := Module[{v, adj, left, ans},
	v = VertexList @ g;
	adj = ToAdjacencyListsBasicNoLoop @ g;
	left = v;
	ans = Part[
		Reap[
			While[Unequal[left, {}],
				vert = left[[1]];
				Sow @ vert;
				left = Complement[Rest @ left, Part[adj, Part[Position[v, vert], 1, 1]]]
			]
		],
		2, 1
	]
];

ToAdjacencyListsBasicNoLoop[g_] := Table[
	DeleteCases[VertexList @ NeighborhoodGraph[g, i], i],
	{i, VertexList @ g}
];

ColoringFromIndSetLPSoln[S2_, sol_] := With[
	{S2Thinned = Part[S2, Flatten[Position[Map[Last, sol], 1 | 1.]]]},
	Table[Part[Position[S2Thinned, vv], 1, 1], {vv, Union @@ S2}]
];

ISByILPDualLP[S_] := Module[{verts, m, b, c, i},
	verts = Union @@ S;
	b = Map[1&, S];
	c = Map[1&, verts];
	m = Table[0, {Length @ S}, {Length @ verts}];
	Do[Part[m, i, Part[S, i]] = 1,
		{i, Length @ S}
	];
	LinearProgramming[-c, -m, -b]
];

ISByILPInteger[S_] := Module[
	{n = Length @ S, v, obj, con0, con1, sol, verts, x},
	v = Map[x, Range @ n];
	obj = Total @ v;
	verts = Union @@ S;
	con0 = {Thread @ LessEqual[0, v, 1], Element[v, Integers]};
	con1Left = Table[
		Total[
			Map[x,
				Select[Range @ n, Function[MemberQ[Part[S, #], j]]]
			]
		],
		{j, verts}
	];
	con1 = Thread @ GreaterEqual[con1Left, 1];
	NMinimize[{obj, Flatten @ {con0, con1}}, v]
];

Static ILP via NMinimize via COIN

VertexColoringByStatic[g_System`Graph/;ConnectedGraphQ[g],opts___?OptionQ]:=Module[{i,sol,inds,S},S=FindAllMaximalIndependentVertexSets[g];
sol=ISByILPInteger[S];
inds=S[[Cases[sol[[2]],HoldPattern[r_[z_]->1]:>z]]];
Table[Position[inds,i][[1,1]],{i,VertexCount[g]}]]/;ConnectedGraphQ[g]

VertexColoringByStatic[g_System`Graph,opts___?OptionQ]:=Module[{comps=Sort/@System`ConnectedComponents[g],c},Sort[Transpose[Flatten/@{comps,Table[VertexColoringByStatic[IndexGraph[System`Subgraph[g,c]],opts],{c,comps}]}]][[All,-1]]]/;!ConnectedGraphQ[g]

ISByILPInteger[S_]:=Module[{n=Length[S],v,obj,con0,con1,verts,x},v=Array[x,n];
obj=Total[v];
verts=Union@@S;
con0={Thread[0≤v≤1],v∈Integers};
con1Left=Table[Total[x/@Select[Range[n],MemberQ[S[[#]],j]&]],{j,verts}];
con1=Thread[con1Left≥1];
NMinimize[{obj,Flatten[{con0,con1}]},v]]

LinearProgramming

From S. Horvat, Apr. 24 2019

ChromaticNumberLinearProgramming[g_Graph]:=Module[{graph=IndexGraph@UndirectedGraph[g],nv=VertexCount[g],ivs,mat},ivs=FindIndependentVertexSet[graph,Infinity,All];
(*mat_{v,s}=1 if vertex v is part of set s*)mat=Transpose[SparseArray[#->ConstantArray[1,Length[#]],{nv}]&/@ivs];
Total@Quiet[LinearProgramming[ConstantArray[1,Length[ivs]],(*minimize number of included independent sets*)mat,ConstantArray[1,nv],(*all vertices must be covered by at least one included set*)0,Integers],LinearProgramming::lpip]]

Compare

c0=GraphData[#,"ChromaticNumber"]&/@GraphData[;;10];//Timing

c1=ChromaticNumberLinearProgramming[GraphData[#]]&/@GraphData[;;10];//Timing

c2=Max[VertexColoringByStatic[GraphData[#]]]&/@GraphData[;;10];//Timing

c3=ChromaticNumberWagon[GraphData[#]]&/@GraphData[;;10];//Timing

c0===c1===c2===c3