An Inequality for Generalized Chromatic Graphs

Details An Inequality for Generalized Chromatic Graphs An Inequality for Generalized Chromatic Graphs

2011-11-23

arxiv.org/abs/1111.5598v1

Mathematics

Combinatorics

5 pages

Scientific paper

Let $G$ be a simple $n$-vertex graph with degree sequence $d_1,d_2,...,d_n$ and vertex set $\V(G)$. The degree of $v\in\V(G)$ is denoted by $\D(v)$. The smallest integer $r$ for which $\V(G)$ has an $r$-partition $$ \V(G)=V_1\cup V_2\cup...\cup V_r,\quad V_i\cap V_j=\emptyset, \quad,i\neq j $$ such that $\D(v)\leq n-\abs{V_i}$, $\forall v\in V_i$, $i=1,2,...,r$ is denoted by $\f(G)$. In this note we prove the inequality $$ \f(G)\geq\frac n{n-\bar{\bar{d}}}, $$ where $\bar{\bar{d}}=\sqrt{\dfrac{d_1^2+d_2^2+...+d_n^2}n}$.

Affiliated with

Also associated with

No associations

Rating

An Inequality for Generalized Chromatic Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Inequality for Generalized Chromatic Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Inequality for Generalized Chromatic Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-378154