Proof of a conjectured lower bound on the chromatic number of a graph

DOI10.1016/j.laa.2015.08.007zbMath1322.05054OpenAlexW1149759637MaRDI QIDQ745214

Minghua Lin, Tsuyoshi Ando

Publication date: 13 October 2015

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2015.08.007

zbMATH Keywords

lower boundchromatic number

Mathematics Subject Classification ID

Miscellaneous inequalities involving matrices (15A45) Coloring of graphs and hypergraphs (05C15)

Related Items (16)

Conjectured bounds for the sum of squares of positive eigenvalues of a graph ⋮ A characterization and an application of weight-regular partitions of graphs ⋮ Positive and negative square energies of graphs ⋮ Two conjectured strengthenings of Turán's theorem ⋮ On the first two eigenvalues of regular graphs ⋮ Spectral bounds for the quantum chromatic number of quantum graphs ⋮ New eigenvalue bound for the fractional chromatic number ⋮ On inertia and ratio type bounds for the \(k\)-independence number of a graph and their relationship ⋮ Unnamed Item ⋮ Upper bounds for the achromatic and coloring numbers of a graph ⋮ An inertial lower bound for the chromatic number of a graph ⋮ Nordhaus-Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph ⋮ Eigenvalues and triangles in graphs ⋮ Spectral lower bounds for the quantum chromatic number of a graph ⋮ On some inequalities for accretive-dissipative matrices ⋮ More tales of Hoffman: bounds for the vector chromatic number of a graph

Cites Work

• Unnamed Item
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• Chromatic number and spectral radius
• Inequalities for the extreme eigenvalues of block-partitioned Hermitian matrices with applications to spectral graph theory

This page was built for publication: Proof of a conjectured lower bound on the chromatic number of a graph