Ask Your Question

chromatic polynomial graph with loops

asked 2019-06-05 14:16:04 +0100

luis gravatar image

updated 2019-06-06 10:12:07 +0100

slelievre gravatar image

Since there are no proper colorings of graphs with loops, their chromatic polynomial should be zero.

SageMath 8.6 however seems to ignore the loops and returns a nonzero chromatic polynomial for the graph on one vertex with one loop edge.

sage: Graph([[1, 1]], multiedges=True, loops=True).chromatic_polynomial()
edit retag flag offensive close merge delete


This indeed looks like a bug. Thanks for reporting!

Would you like to open a ticket for it on the Sage Trac server?

Would you like to suggest a fix? The relevant file is

(If not, I can take care of it.)

slelievre gravatar imageslelievre ( 2019-06-06 10:37:52 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2019-06-06 10:43:54 +0100

slelievre gravatar image

This indeed looks like a bug.

As a workaround, test whether the graph has loops before computing the chromatic polynomial.

sage: G = Graph([[1, 1]], multiedges=True, loops=True)
sage: G.has_loops()

Fixing the bug should just amount to special-casing graphs with loops (testing for loops as above) and including a doctest (to prevent the bug from reappearing).

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


Asked: 2019-06-05 14:16:04 +0100

Seen: 85 times

Last updated: Jun 06 '19