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
.
Paru en octobre 2006 , 16 pages
Axe de recherche
Applications de recherche
Publication
jan. 2009
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