pith. sign in

arxiv: 1903.03821 · v1 · pith:DT5OQOMInew · submitted 2019-03-09 · 🧮 math.CO

Equality cases for a bound on the chromatic number

classification 🧮 math.CO
keywords chromaticequalitygraphholdsnumberattachedboundcases
0
0 comments X
read the original abstract

It is known that the inequality $$ \frac{\chi(G)(\chi(G)-1)}{2} + |V| - \chi(G) \leq |E|$$ holds for all connected graphs, where $\chi(G)$ denotes the chromatic number of $G$. We prove that equality holds whenever the graph consists of a complete graph or an odd cycle, together with finitely many trees attached to its vertices.

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.