5
$\begingroup$
  1. Let $G=(V,E)$ be a graph whose vertices can be colored with $m$-colors, such that each color appears at least twice.

  2. Let $\lambda(G)$ denote the minimum number of colors needed for a vertex-coloring of $G$

Use 1. to prove that such a coloring can be achieved with $\lambda(G)$ colors

Let $\alpha$ denote a coloring with property 1. and $\beta$ a coloring with $\lambda(G)$ colors. $\beta$ has a color class with only one vertex if $\beta$ doesn't have property 1.

I don't know how that helps to prove that such a coloring can be achieved with $\lambda(G)$ colors

Edit: A coloring of the graph $G$ is a proper coloring. $u,v$ have different colors if $(u,v)\in E$

Would appreciate any help

$\endgroup$
  • $\begingroup$ In 1 and 2, are the colorings supposed to be proper colorings, i.e., adjacent vertices have different colors? $\endgroup$ – bof Jun 17 '18 at 23:35
  • $\begingroup$ Is $\lambda(G)$ the chromatic number of $G$? If so, why do you use $\lambda$ instead of the usual $\chi$? $\endgroup$ – bof Jun 17 '18 at 23:44
  • $\begingroup$ Why do you not reply to comments? $\endgroup$ – bof Jun 19 '18 at 1:09
  • $\begingroup$ @bof Sry, you're right. The vertex coloring is supposed to be a proper coloring and I used $\lambda$ because the script I am learning from used it as well $\endgroup$ – XPenguen Jun 19 '18 at 1:30
  • $\begingroup$ @bof You can repost your answer again If you don't think there is anything wrong with it. I was going to accept your answer, it's just that I hadn't checked the site the last couple of days. $\endgroup$ – XPenguen Jun 19 '18 at 1:35
3
+50
$\begingroup$

Call the given coloring with at least two vertices of each color a friendly coloring.

Now start with the coloring that uses the minimal number of colors. If every color is used twice we are done. If not, pick a vertex with a lonely color, look up the vertices that share its color in the friendly coloring and repaint them with the lonely color. Repeat as long as there are lonely vertices.

It is clear that this always gives an admissible coloring and that it does not increase the number of colors. But the procedure must stop because a repainted vertex will not be repainted again. So we end up with a friendly minimal coloring.

$\endgroup$

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.