Retour

G-2006-58

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

et

référence BibTeX

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

Axe de recherche

Applications de recherche

Publication

Variable neighborhood search for extremal graphs. 23. On the Randic index and the chromatic number
et
Discrete Applied Mathematics, 309(13), 4228–4234, 2009 référence BibTeX