Let $G$ be a graph with vertex set $V=\{1,2,\dots,2005\}$. Two distinct vertices $i,j\in V$ are adjacent iff $i+j\equiv1\pmod{3}$.
What is the chromatic number and independent edges?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this communityLet $G$ be a graph with vertex set $V=\{1,2,\dots,2005\}$. Two distinct vertices $i,j\in V$ are adjacent iff $i+j\equiv1\pmod{3}$.
What is the chromatic number and independent edges?
Divide your vertices into three classes: $$ V_0=\text{all vertices whose labels are congruent to }0\pmod3\\ V_1=\text{all vertices whose labels are congruent to }1\pmod3\\ V_2=\text{all vertices whose labels are congruent to }2\pmod3. $$
Then the graph on $V_0$ and $V_1$ will be a complete bipartite graph and $V_2$ will be a clique. There will be no edges from $V_2$ to either $V_0$ or $V_1$.
Thus the chromatic number is the order of the clique on $V_2$ and the size of a maximal set of independent edges $M$ will be the size of the maximal matching between $V_0$ and $V_1$ plus the size of the maximal matching in the clique on $V_2$. Thus $$ \lvert M\rvert= \min\{\lvert V_0\rvert,~\lvert V_1\rvert\}+\left\lfloor \left\lvert \frac{V_2}{2}\right\rvert\right\rfloor. $$