New eigenvalue bound for the fractional chromatic number

DOI10.1002/JGT.23071MaRDI QIDQ6201030zbMATH OpenOpenAlexFDO

Authors Krystal Guo, Sam Spiro

Publication date 25 March 2024

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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

zbMATH Keywords

fractional chromatic numbergraph eigenvaluesspectral graph theory

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Fractional graph theory, fuzzy graph theory (05C72) Association schemes, strongly regular graphs (05E30) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: Given a graph $G$, we let $s^{+}(G)$ denote the sum of the squares of the positive eigenvalues of the adjacency matrix of $G$, and we similarly define $s^{-}(G)$. We prove that [chi_f(G)ge 1+maxleft{frac{s^+(G)}{s^-(G)},frac{s^-(G)}{s^+(G)} ight}] and thus strengthen a result of Ando and Lin, who showed the same lower bound for the chromatic number $chi(G)$. We in fact show a stronger result wherein we give a bound using the eigenvalues of $G$ and $H$ whenever $G$ has a homomorphism to an edge-transitive graph $H$. Our proof utilizes ideas motivated by association schemes.

Recommendations

• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• Eigenvalues and chromatic number of a signed graph
• An inertial lower bound for the chromatic number of a graph
• A lower bound for the chromatic number of a graph
• Chromatic number and spectral radius

Cites work

• A comparison of the Delsarte and Lovász bounds
• An inertial lower bound for the chromatic number of a graph
• Chromatic number and spectral radius
• Eigenvalues and colorings of digraphs
• Erdős-Ko-Rado theorems. Algebraic approaches
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3425628 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• More tales of Hoffman: bounds for the vector chromatic number of a graph
• New bounds for the -k-cut and chromatic number of a graph
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• On some inequalities for accretive-dissipative matrices
• On the chromatic number of a simplicial complex
• Proof of a conjectured lower bound on the chromatic number of a graph
• Spectra of uniform hypergraphs
• Spectral bounds for the quantum chromatic number of quantum graphs
• Spectral lower bounds for the quantum chromatic number of a graph
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• The Eigenvalues of a Graph and Its Chromatic Number

Cited in

(5)

• A spectral lower bound on chromatic numbers using p-energy
• Random independent sets in triangle-free graphs
• Vertex partitioning and p-energy of graphs
• A note on the Bollobás-Nikiforov conjecture
• Two chromatic numbers, eigenvalues and a generalized Lovász theta

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: New eigenvalue bound for the fractional chromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201030)