An inertial lower bound for the chromatic number of a graph

MaRDI QIDQ521386zbMATH OpenFDO

Authors Clive Elphick, Pawel Wocjan

Publication date 10 April 2017

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

Full work available at URL https://arxiv.org/abs/1605.01978, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p58

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• A survey of Nordhaus-Gaddum type relations
• Chromatic number and spectral radius
• Erdős-Ko-Rado theorems. Algebraic approaches
• Extrema of graph eigenvalues
• Inequalities for the extreme eigenvalues of block-partitioned Hermitian matrices with applications to spectral graph theory
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers
• On Complementary Graphs
• Proof of a conjectured lower bound on the chromatic number of a graph
• Spectra of graphs
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• The smallest eigenvalue of the signless Laplacian
• 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)