Algebraic Bounds for the Independence and Chromatic Number of Graph Powers
Authors:
- 1 April 2026
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 47 (2) , 467-482
Abstract
The \(k\)th graph power \(G^k\) of a graph \(G = (V , E)\) is the graph whose vertex set is \(V\) and in which two distinct vertices are adjacent if and only if their distance in \(G\) is...
Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (12071097)
- National Natural Science Foundation of China (12371344)
- Natural Science Foundation of Heilongjiang Province (YQ2024A009)
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek (VI.Vidi.213.085)
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek (OCENW.KLEIN.475)
This publication has 46 references indexed in Scilit:
- On the chromatic number of powers of subdivisions of graphsDiscrete Applied Mathematics, 2024
- On inertia and ratio type bounds for the -independence number of a graph and their relationshipDiscrete Applied Mathematics, 2023
- Sharp Upper Bounds on the k-Independence Number in Graphs with Given Minimum and Maximum DegreeGraphs and Combinatorics, 2020
- Orthonormal Representations of H-Free GraphsDiscrete & Computational Geometry, 2020
- Rainbow Connection Number of Graph Power and Graph ProductsGraphs and Combinatorics, 2013
- Average Degree in Graph PowersJournal of Graph Theory, 2012
- Spectra of Graphs2012
- Tree PowersJournal of Algorithms, 1998
- Interlacing eigenvalues and graphsLinear Algebra and its Applications, 1995
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981