Optimization of eigenvalue bounds for the independence and chromatic number of graph powers

DOI10.1016/j.disc.2021.112706zbMath1481.05092arXiv2010.12649OpenAlexW3216457453MaRDI QIDQ2065879

S. Zeijlemaker, Aida Abiad, B. D. Nogueira, Gabriel Coutinho, Miquel Àngel Fiol

Publication date: 13 January 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2010.12649

zbMATH Keywords

eigenvaluesindependence numberchromatic number\(k\)-power graph

Mathematics Subject Classification ID

Integer programming (90C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Characterizing and computing weight-equitable partitions of graphs ⋮ The optimal bound on the 3-independence number obtainable from a polynomial-type method ⋮ On inertia and ratio type bounds for the \(k\)-independence number of a graph and their relationship ⋮ Spectral upper bound on the quantum k-independence number of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantum homomorphisms
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• Spectral bounds for the \(k\)-independence number of a graph
• An inertial lower bound for the chromatic number of a graph
• Some spectral and quasi-spectral characterizations of distance-regular graphs
• Locally pseudo-distance-regular graphs
• Feasibility conditions for the existence of walk-regular graphs
• Ovoids and spreads of finite classical polar spaces
• Polarities of generalized hexagons and perfect codes
• The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs
• Eigenvalue interlacing and weight parameters of graphs
• Algebraic characterizations of distance-regular graphs
• The alternating polynomials and their relation with the spectra and conditional diameters of graphs
• Independence and average distance in graphs
• From local adjacency polynomials to locally pseudo-distance-regular graphs
• Multidiameters and multiplicities
• Interlacing eigenvalues and graphs
• Coloring the normalized Laplacian for oriented hypergraphs
• A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number
• On the \(k\)-independence number of graphs
• On almost distance-regular graphs
• Sharp upper bounds on the \(k\)-independence number in graphs with given minimum and maximum degree
• Coloring Powers and Girth
• Integer Programming with a Fixed Number of Variables
• On the Shannon capacity of a graph
• The Chromatic Number of Graph Powers
• The strong chromatic index ofC4-free graphs
• On the $b$ -Independence Number of Sparse Random Graphs
• Distance Colouring Without One Cycle Length
• Spectral upper bound on the quantum k-independence number of a graph
• Recursive Formulas for Beans Functions of Graphs
• CORES OF SYMMETRIC GRAPHS
• 2-Transitive Symmetric Designs

This page was built for publication: Optimization of eigenvalue bounds for the independence and chromatic number of graph powers