G-2006-58
Variable Neighborhood Search for Extremal Graphs. 23. On the Randic Index and the Chromatic Number
and BibTeX reference
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
Research Axis
Research applications
Publication
Jan 2009
Variable neighborhood search for extremal graphs. 23. On the Randic index and the chromatic number
and
Discrete Applied Mathematics, 309(13), 4228–4234, 2009
BibTeX reference