The geometric-arithmetic index and the chromatic number of connected graphs

被引：7

作者：

Aouchiche, Mustapha ^{[1
]}

Hansen, Pierre

机构：

[1] Gerad, Montreal, PQ, Canada

来源：

DISCRETE APPLIED MATHEMATICS | 2017年 / 232卷

关键词：

Graph; Geometric-arithmetic index; Chromatic number; Clique number; Conjecture; VARIABLE NEIGHBORHOOD SEARCH; EXTREMAL GRAPHS;

D O I：

10.1016/j.dam.2017.08.003

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In the present paper, we compare the geometric-arithmetic index GA and the chromatic number chi of a connected graph with given order. We prove, among other results, an upper bound on the ratio GA/chi. We also prove lower bounds on the chromatic number in terms of geometric-arithmetic index and number of vertices of a connected graph. The results obtained for the chromatic number chi are extended to the clique number omega. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：207 / 212

页数：6

共 28 条

[1] Ali A., 2014, ARXIV14017511
[2] [Anonymous], 1890, Quart. J. Math.
[3] [Anonymous], 1879, Am. J. Math., DOI DOI 10.2307/2369235
[4] [Anonymous], 2008, The mathematical coloring book: Mathematics of coloring and the colorful life of its creators
[5] [Anonymous], 2008, Handbook of molecular descriptors
[6] Aouchiche M, 2006, NONCON OPTIM ITS APP, V84, P281
[7] Aouchiche M, 2007, MATCH-COMMUN MATH CO, V58, P365
[8] Biggs N., 1986, GRAPH THEORY 1736 19
[9] Variable neighborhood search for extremal graphs. 5. Three ways to automate finding conjectures
Caporossi, G
Hansen, P
[J]. DISCRETE MATHEMATICS, 2004, 276 (1-3) : 81 - 94
[10] Variable neighborhood search for extremal graphs: 1 The AutoGraphiX system
Caporossi, G
Hansen, P
[J]. DISCRETE MATHEMATICS, 2000, 212 (1-2) : 29 - 44

← 1 2 3 →