Ask Your Question
0

How to get a list of graphs whose independence number equals to chromatic number?

asked 2014-09-20 22:13:53 -0600

this post is marked as community wiki

This post is a wiki. Anyone with karma >750 is welcome to improve it.

  1. The smallest number of colors needed to color a graph G is called its chromatic number, and is often denoted χ(G).

  2. The independence number α(G) of a graph G is the size of the largest independent set of G.

edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted
2

answered 2014-09-22 07:51:43 -0600

kcrisman gravatar image

It turns out that chromatic number is easy to find.

sage: G = graphs(6)
sage: g = G.next()
sage: g.chromatic_number()
1

By the way, to find out what you can do with a graph you can do

sage: g.?

and a list of all methods will appear, including this one.

However, I believe the syntax for your other thing is

sage: g.independent_set(value_only=True)
6

This fact is hidden here in the documentation. Perhaps it should be a separate command if this is a common invariant?

Anyway, then you can use a basic filtered list comprehension to finish it off.

sage: [g for g in graphs(3) if g.chromatic_number()==g.independent_set(value_only=True)]
[Graph on 3 vertices, Graph on 3 vertices]
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

2 followers

Stats

Asked: 2014-09-20 22:13:53 -0600

Seen: 462 times

Last updated: Sep 22 '14