IGraph/M has excellent graph colouring functionality, and I now recommend it over Combinatorica.
<< IGraphM`
Graph[gr, VertexSize -> Large] //
IGVertexMap[ColorData[105], VertexStyle -> IGMinimumVertexColoring]

There are two problems:
Combinatorica is an obsolete package and many of the function/symbol names conflict with new, builtin ones. You'll need to refer to these symbols with their fully qualified name, e.g. System`Graph
and Combinatorica`Graph
. Whenever a symbol name is shown in red, you'll need to prepend a context to indicate whether you're referring to a symbol from Combinatorica of the System`
context.
Combinatorica has been around much longer than the builtin graph datatype and has its own distinct graph representation. You'll need to convert the graph to this format using ToCombinatoricaGraph
from the GraphUtilities`
package.
<< Combinatorica`
<< GraphUtilities`
gr = System`Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9}, {1 <-> 2, 1 <-> 3,
1 <-> 7, 1 <-> 9, 2 <-> 3, 2 <-> 5, 2 <-> 6, 2 <-> 7, 3 <-> 4,
3 <-> 5, 3 <-> 9, 4 <-> 5, 4 <-> 6, 4 <-> 8, 4 <-> 9, 5 <-> 6,
6 <-> 7, 6 <-> 8, 7 <-> 8, 7 <-> 9, 8 <-> 9},
VertexCoordinates -> {{0, 2}, {1, 1}, {-1, 1}, {-1, -1}, {0,
0}, {1, -1}, {8, 4}, {0, -2}, {-8, 4}}, VertexLabels -> "Name",
VertexSize -> Large]
mvc = MinimumVertexColoring@ToCombinatoricaGraph[gr]
SetProperty[gr,
System`VertexStyle ->
Thread[System`VertexList[gr] -> (ColorData[97] /@ mvc)]]

Note: This trick is unfortunately not useful here because GraphUtilities`ToCombinatoricaGraph
evaluates Needs["Combinatorica`"]
each time it's evaluated, re-adding Combinatorica`
to the context path. I have suggested fixing this to WRI on multiple accounts, but so far they haven't done it.