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

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 close merge delete

Sort by » oldest newest most voted

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]

more