0
$\begingroup$

Let $G$ be a simple connected finite graph and let $v \ge 4$ be the number of vertices, $E$ the number of edges, $\chi(G)$ the chromatic number , $\omega(G)$ the clique number and $\Delta$ the maximum degree of G. Let $C(G)$ be a function of $G$ which is equal to $3$ when $G$ contains cycles of odd length. Let $ {(d_1,d_2,...)}$ be the degree sequence of G.

Let $i > 4$ be the smallest integer such that

$$ \left\lceil \frac{(0.5\sum\limits_{j=1}^i d_j) -i}{i-3} \right\rceil < \frac{i}{2}$$

and

$$ 2\frac{(0.5\sum\limits_{j=1}^i d_j) -i}{i-3} < \Delta $$

Take $i = v$ if a minimum value does not exist.

Let

$ B = 4 $ if $$ 1.5\leq\frac{(0.5\sum\limits_{j=1}^i d_j) -i}{i-3} < 2 $$

Otherwise

$$ B = \left\lfloor 2\frac{(0.5\sum\limits_{j=1}^i d_j) -i}{i-3} \right\rfloor $$

Then

$$\chi(G) \le \max\left\{C(G) \ , B,\ \omega(G)\right\}$$

$\endgroup$
2
  • $\begingroup$ Probably your summation index should be $j=1$, rather than $i=1$? $\endgroup$ Jan 9, 2015 at 1:51
  • 3
    $\begingroup$ Could you provide the concept/motivation? (Is $\ 0.5\ $ simply $\ \frac 12\ $ and $\ 1.5=\frac 32)\ $? $\endgroup$ Jan 10, 2015 at 18:55

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.