Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
3-Coloring given the adjacency matrix?

Subject: 3-Coloring given the adjacency matrix?

From: Apostol

Date: 27 Jan, 2012 02:26:09

Message: 1 of 4

Hello guys!
Does anybody know where can I find a function that colors a graph with 3 colors? e.g. given an adjacency matrix the output would be a vector saying which node belongs to which group/color?

Thanks :)

Subject: 3-Coloring given the adjacency matrix?

From: Apostol

Date: 27 Jan, 2012 19:43:10

Message: 2 of 4

Nobody? :/ Any idea on how i can use a maxcut for a bi-partition and make it a tri-partition?

Subject: 3-Coloring given the adjacency matrix?

From: Andreas Lobinger

Date: 28 Jan, 2012 14:41:47

Message: 3 of 4

On Fri, 27 Jan 2012 19:43:10 +0000, Apostol wrote:

> Nobody? :/ Any idea on how i can use a maxcut for a bi-partition and
> make it a tri-partition?

You are aware that in only a limited number of cases a 3coloring is
available?

I have something like a n-coloring available that uses a heuristic to
color with a minimum set, but even in some cases it's rather 3+1 colors.

Subject: 3-Coloring given the adjacency matrix?

From: Bruno Luong

Date: 28 Jan, 2012 15:12:10

Message: 4 of 4

"Apostol" wrote in message <jft201$er4$1@newscl01ah.mathworks.com>...
> Hello guys!
> Does anybody know where can I find a function that colors a graph with 3 colors? e.g. given an adjacency matrix the output would be a vector saying which node belongs to which group/color?

Do you mean to color so the any adjacent vertexes do not have the same color?

You can't using three colors for such graph:

 A=[0 1 1 1;
      1 0 1 1;
      1 1 0 1;
      1 1 1 0]

What to do?

Bruno

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us