An inertial lower bound for the chromatic number of a graph

zbMATH Open1358.05104arXiv1605.01978MaRDI QIDQ521386FDOQ521386

Authors: Clive Elphick, Pawel Wocjan 

Publication date: 10 April 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $chi(G$) and $ch{i}_f(G)$ denote the chromatic and fractional chromatic numbers of a graph $G$, and let $(n^{+},n^0,n^{-})$ denote the inertia of $G$. We prove that: [ 1 + maxleft(frac{n^+}{n^-} , frac{n^-}{n^+} ight) le chi(G) mbox{ and conjecture that } 1 + maxleft(frac{n^+}{n^-} , frac{n^-}{n^+} ight) le chi_f(G) ] We investigate extremal graphs for these bounds and demonstrate that this inertial bound is not a lower bound for the vector chromatic number. We conclude with a discussion of asymmetry between $n^{+}$ and $n^{-}$, including some Nordhaus-Gaddum bounds for inertia.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• Chromatic number and spectral radius
• Eigenvalues and chromatic number of a signed graph
• A graph for which the inertia bound is not tight
• More tales of Hoffman: bounds for the vector chromatic number of a graph

zbMATH Keywords

spectral graph theorychromatic numberfractional chromatic number

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Spectra of graphs
• Extrema of graph eigenvalues
• The smallest eigenvalue of the signless Laplacian
• Erdős-Ko-Rado theorems. Algebraic approaches
• Chromatic number and spectral radius
• A survey of Nordhaus-Gaddum type relations
• On Complementary Graphs
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• Proof of a conjectured lower bound on the chromatic number of a graph
• Title not available (Why is that?)
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• Inequalities for the extreme eigenvalues of block-partitioned Hermitian matrices with applications to spectral graph theory
• Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers
• Unified spectral bounds on the chromatic number

Cited In (11)

• On the difference of energies of a graph and its complement graph
• Two conjectured strengthenings of Turán's theorem
• Spectral lower bounds for the orthogonal and projective ranks of a graph
• A characterization and an application of weight-regular partitions of graphs
• Spectral bounds for the quantum chromatic number of quantum graphs
• The inertia bound is far from tight
• New eigenvalue bound for the fractional chromatic number
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• Spectral lower bounds for the quantum chromatic number of a graph
• Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming
• A graph for which the inertia bound is not tight

This page was built for publication: An inertial lower bound for the chromatic number of a graph

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