Let be a simple graph with vertex degrees . The Randic index is equal to the sum over all edges of weights . We prove several conjectures, obtained by the system AutoGraphiX, relating and the chromatic number . The main result is . To prove it, we also show that if is a vertex of minimum degree of , the graph obtained from by deleting and all incident edges, and the maximum degree of , then .
Published October 2006 , 16 pages