pith. machine review for the scientific record. sign in

arxiv: 1605.01978 · v4 · submitted 2016-05-06 · 🧮 math.CO

Recognition: unknown

An inertial lower bound for the chromatic number of a graph

Authors on Pith no claims yet
classification 🧮 math.CO
keywords chromaticfracboundboundsdenotegraphinertiainertial
0
0 comments X
read the original abstract

Let $\chi(G$) and $\chi_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 + \max\left(\frac{n^+}{n^-} , \frac{n^-}{n^+}\right) \le \chi(G) \mbox{ and conjecture that } 1 + \max\left(\frac{n^+}{n^-} , \frac{n^-}{n^+}\right) \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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. BBQ-mIS: a parallel quantum algorithm for graph coloring problems

    quant-ph 2026-05 unverdicted novelty 5.0

    BBQ-mIS decomposes graph coloring into parallel maximum independent set instances on Rydberg quantum hardware combined with classical branch-and-bound to produce proper colorings with few colors.