0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is $2$ adjacent to itself? $\endgroup$ – ajotatxe Apr 17 '17 at 14:21
  • 1
    $\begingroup$ no, two different vertices must necessary $\endgroup$ – maki Apr 17 '17 at 14:22
  • $\begingroup$ 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? $\endgroup$ – coffeemath Apr 17 '17 at 14:35
  • $\begingroup$ independent edges are no two of which are adjacent. $\endgroup$ – maki Apr 17 '17 at 14:38
  • $\begingroup$ So, are you looking for the size of the largest set of pairwise independent edges, or what? $\endgroup$ – bof Apr 18 '17 at 4:23
1
$\begingroup$

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. $$

$\endgroup$
  • $\begingroup$ In normal usage, two edges are adjacent if they are both incident with a common vertex (just as two vertices are adjacent if they are both incident with a common edge), and two edges are independent if they are not adjacent. There will be lots of independent edges. $\endgroup$ – bof Apr 18 '17 at 4:22
  • $\begingroup$ 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$. $\endgroup$ – Laars Helenius Apr 18 '17 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.