# Chromatic Number, independent edges of a graph

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?

• Is $2$ adjacent to itself? – ajotatxe Apr 17 '17 at 14:21
• no, two different vertices must necessary – maki Apr 17 '17 at 14:22
• So you want the chromatic number, but what are you counting or to find in "independent edges"? When are two edges said to be independent? – coffeemath Apr 17 '17 at 14:35
• independent edges are no two of which are adjacent. – maki Apr 17 '17 at 14:38
• So, are you looking for the size of the largest set of pairwise independent edges, or what? – bof Apr 18 '17 at 4:23

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.$$
• Ah, then the size of a maximal set of independent edges 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$. – Laars Helenius Apr 18 '17 at 13:08