Eigenvalues and chromatic number of a signed graph

被引：8
|
作者：
Wang, Wei [1 ]
Yan, Zhidan [1 ]
Qian, Jianguo [2 ]
机构：
[1] Anhui Polytech Univ, Sch Math Phys & Finance, Wuhu 241000, Peoples R China
[2] Xiamen Univ, Sch Math Sci, Xiamen 361005, Peoples R China
来源：
LINEAR ALGEBRA AND ITS APPLICATIONS | 2021年 / 619卷
基金：
中国国家自然科学基金;
关键词：
Signed graph; Eigenvalue; Chromatic number; Clique; SPECTRAL BOUNDS; CLIQUE;
D O I：
10.1016/j.laa.2021.02.018
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
For a signed graph Sigma, let chi(Sigma), lambda(1) and lambda(n) be the chromatic number, the maximum eigenvalue and the minimum eigenvalue of Sigma, respectively. This paper proves that, for any nonempty signed graph Sigma with n vertices, chi(Sigma) >= max {1 + lambda(1)/vertical bar lambda(n)vertical bar, n/n - lambda(1)}. These two bounds extend the classical spectral lower bounds of Hoffman and Cvetkovic for an ordinary graph, respectively. (C) 2021 Elsevier Inc. All rights reserved.
引用
收藏
页码：137 / 145
页数：9
相关论文
共 50 条
  • [21] The Sigma Chromatic Number of a Graph
    Chartrand, Gary
    Okamoto, Futaba
    Zhang, Ping
    GRAPHS AND COMBINATORICS, 2010, 26 (06) : 755 - 773
  • [22] The Singular Chromatic Number of a Graph
    Kolasinski, Kyle
    Lin, Jianwei
    Lumduanhom, Chira
    Phinezy, Bryan
    Okamoto, Futaba
    ARS COMBINATORIA, 2015, 118 : 13 - 31
  • [23] CHROMATIC NUMBER OF A SIMPLE GRAPH
    SCHMEICH.EF
    AMERICAN MATHEMATICAL MONTHLY, 1971, 78 (02): : 205 - &
  • [24] TOTAL CHROMATIC NUMBER OF A GRAPH
    VIJAYADITYA, N
    JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 1971, 3 (APR): : 405 - +
  • [25] The Sigma Chromatic Number of a Graph
    Gary Chartrand
    Futaba Okamoto
    Ping Zhang
    Graphs and Combinatorics, 2010, 26 : 755 - 773
  • [26] An approximate chromatic number of a graph
    Marcu, Danut
    JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2008, 11 (04): : 461 - 464
  • [27] THE STAR CHROMATIC NUMBER OF A GRAPH
    ABBOTT, HL
    ZHOU, B
    JOURNAL OF GRAPH THEORY, 1993, 17 (03) : 349 - 360
  • [28] On the quantum chromatic number of a graph
    Cameron, Peter J.
    Montanaro, Ashley
    Newman, Michael W.
    Severini, Simone
    Winter, Andreas
    ELECTRONIC JOURNAL OF COMBINATORICS, 2007, 14 (01):
  • [29] The chromatic covering number of a graph
    Naserasr, R
    Tardif, C
    JOURNAL OF GRAPH THEORY, 2006, 51 (03) : 199 - 204
  • [30] The chromatic number of graph powers
    Alon, N
    Mohar, B
    COMBINATORICS PROBABILITY & COMPUTING, 2002, 11 (01): : 1 - 10
12345