Groupe d’études et de recherche en analyse des décisions

G-2006-58

Variable Neighborhood Search for Extremal Graphs. 23. On the Randic Index and the Chromatic Number

et

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  .

, 16 pages