Share
Explore BrainMass

Vertex Chromatic Numbers and Betti Numbers

Prove for every graph G of order n, that n/B(G)<=X(G)<=n+1-B(G).

X(G) is the minimum integer k for which a graph G is k-colorable is called the vertex chromatic number

In the page 82 B(G) is defined like independent sets like you say but in the page 187 it other kind of B and it is define like Betti number and it is defined below

B(G) is the Betti number of the graph G of order n and size m having k components and it is defined as B(G)=m-n+k.

You can see on the page 187 of "Graph and Digraphs" 4 edition of G Chartrand and L. Lesniak.

Please can you explain what does B(G) mean and draw a graph.

Solution Summary

Vertex Chromatic Numbers and Betti Numbers are investigated.

$2.19