An Inertial Lower Bound For The Chromatic Number Of A Graph

Keywords

Chromatic number; Fractional chromatic number; Spectral graph theory

Abstract

Letχ(G) and χf (G) denote the chromatic and fractional chromatic numbers of a graph G, and let (n+; n0; n-) denote the inertia of G. We prove that: (Formula Presented) and conjecture that (Formula Presented) 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.

Publication Date

3-31-2017

Publication Title

Electronic Journal of Combinatorics

Volume

24

Issue

1

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.37236/6404

Socpus ID

85017035303 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85017035303

This document is currently not available here.

Share

COinS