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?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Is $2$ adjacent to itself? $\endgroup$– ajotatxeApr 17, 2017 at 14:21
-
1$\begingroup$ no, two different vertices must necessary $\endgroup$– makiApr 17, 2017 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$– coffeemathApr 17, 2017 at 14:35
-
$\begingroup$ independent edges are no two of which are adjacent. $\endgroup$– makiApr 17, 2017 at 14:38
-
$\begingroup$ So, are you looking for the size of the largest set of pairwise independent edges, or what? $\endgroup$– bofApr 18, 2017 at 4:23
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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. $$
answered Apr 18, 2017 at 4:11
-
$\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$– bofApr 18, 2017 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$ Apr 18, 2017 at 13:08