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.

Avoid using Combinatorica if you can. It is not supported any more and therefore not easy to use. It also shadows (= "conflicts with") several builtin functions.

There is indeed some functionality which is only available in Combinatorica. If you do need to use it, prefix your function/symbol names with the appropriate context to disambiguate whether you want the builtin one or the Combinatorica one. It's best if you always do this with symbol names that are coloured red.

It is also a good idea to get the Pemmaraju & Skiena book as there is no other documentation for Combinatorica.

The most important thing to keep in mind: System`Graph and CombinatoricaGraph`` are two distinct, unrelated and incompatible things. They cannot be mixed. Builtin functions work on builtin graphs only. Combinatorica functions work on Combinatorica graphs only.

You can convert between them using the GraphUtilities package.

Example:

<< Combinatorica`

<< GraphUtilities`

At this point, do not refer to Graph anymore without explicitly specifying which one you mean.

Writing Graph[{1<->2}] is no longer valid because Graph now refers to Combinatorica`Graph. So let's be explicit from now on.

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

Combinatorica`MinimumVertexColoring[
 ToCombinatoricaGraph[g]
 ]

(* {1, 2} *)

If you work with graph, also take a look at my IGraph/M package which provides graph-related functionality not available with builtins. It is an interface to igraph.

When CompleteGraph[2] appears to work for you and Graph[{1<->2}] doesn't my first thought is to use FullForm on each of those and see how they differ. Perhaps that can provide you with the needed information to be able to construct your own graphs manually and see if they will work.

There seems to be some inconsistencies between the kernel and the package versions of the combinatorica functions. I suspect that is why both versions are supplied. I have not spent the time to see if there is documentation available explaining the fine details of the changes in combinatorica. Having that information would be very helpful.

I remember finding a perplexing problem in the past when I manually fabricated a graph instead of using the graph construction primitives to build it.

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