Prove or disprove this upper bound on chromatic number.

473 Views Asked by At

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\}$$

===================================================

I've edited it completely because of bof's answer.

** I'm not too sure if this lower bound should be 1 or 1.5.

1

There are 1 best solutions below

0
On

Counterexample. Let $G$ be any graph with $\chi(G)=4$ and $\omega(G)\le3$, and add enough isolated vertices to make $\frac{2(E-v)}{v-3}\le3$.

Maybe you were tacitly assuming that $G$ is connected. That doesn't matter; the wheel graph $W_6$ (also known as $W_5$), obtained by adding a sixth vertex to a $5$-cycle and edges joining it to all of the old vertices, is a connected graph with $\chi=4$, $\omega=3$, $v=6$ and $E=10$.

Edited on account of OP's revised question:

Take the $6$-vertex wheel graph $W_6$, add one new vertex, and one new edge joining the new vertex to one of the old vertices. The resulting graph $G$ is connected and has $\chi=4$, $\omega=3$, $v=7$, $E=11$, and $\frac{2(E-v)}{v-3}=2$; also, $4v-6=2E$.

Edit: another shot at a moving target.

Let $v_0$ be any vertex of the $6$-vertex wheel $W_6$. Add $7$ new vertices $v_1,v_2,v_3,v_4,v_5,v_6,v_7$ and $7$ new edges $v_0v_1,v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_6,v_6v_7$. The resulting graph $G$ is connected and has $v=13$ vertices and $E=17$ edges. It has chromatic number $\chi(G)=4$, clique number $\omega(G)=3$, minimum degree $\delta(G)=1$, and $n=1$ since $v_7$ is the only vertex of degree $1$. Now $\frac{2(E-v)+n}{v-3}=0.9$ and so $\left\lceil\frac{2(E-v)+n}{v-3}\right\rceil+1=2$.