Maybe it's easier to work with Combinatorica this way:

First we load these package without adding them to the context path.

Block[{$ContextPath}, Needs["Combinatorica`"]; Needs["GraphUtilities`"]]

Now System` context symbols are not shadowed. But we must explicitly write the context to call any function from these packages.

I prefer this because it enforces a clear rule and it avoids shadowing altogether.

The function GraphUtilities`ToCombinatoricaGraph has a quirk: it evaluates Needs["Combinatorica"]` every time it's called, and this re-adds this package to the context path. To prevent this, we define our own special version:

toCombinatoricaGraph[g_?GraphQ] := 
 Block[{$ContextPath}, GraphUtilities`ToCombinatoricaGraph[g]]

We can now do this:

g = Graph[{1 <-> 2}];

Combinatorica`MinimumVertexColoring[toCombinatoricaGraph[g]]

We don't need to type System`Graph any more.

I suggested a few times to Wolfram Support to change ToCombinatoricaGraph so that it wouldn't add Combinatorica to the context path and make all this easier on users. But I guess no more changes will be done to unsupported packages.

I believe the Combinatorica package was originally written by Pemmaraju and Skiena outside of Wolfram Inc. They wrote "Computational Discrete Mathematics Combinatorics and Graph Theory with Mathematica(r)" and there are used copies of that available at bargain prices. I urge anyone thinking of using Combinatorica to buy a copy of that.

Later Wolfram Inc. incorporated the Combinatorica package into the Mathematica kernel. This has caused some confusion. The original package is still available if you pull that in.

In[1]:= Needs["Combinatorica`"];
g = CompleteGraph[2];
MinimumVertexColoring[g]

During evaluation of In[1]:= General::compat: Combinatorica Graph and Permutations functionality has been
superseded by preloaded functionality. The package now being loaded may conflict with this. Please see the
Compatibility Guide for details.

Out[3]= {1, 2}

In[4]:= ChromaticNumber[g]

Out[4]= 2