Vol. 8, No. 5, 2015

Download this article
Download this article For screen
For printing
Recent Issues

Volume 11, 1 issue

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
The chromatic polynomials of signed Petersen graphs

Matthias Beck, Erika Meza, Bryan Nevarez, Alana Shine and Michael Young

Vol. 8 (2015), No. 5, 825–831
Abstract

Zaslavsky proved in 2012 that, up to switching isomorphism, there are six different signed Petersen graphs and that they can be told apart by their chromatic polynomials, by showing that the latter give distinct results when evaluated at 3. He conjectured that the six different signed Petersen graphs also have distinct zero-free chromatic polynomials, and that both types of chromatic polynomials have distinct evaluations at any positive integer. We developed and executed a computer program (running in SAGE) that efficiently determines the number of proper k-colorings for a given signed graph; our computations for the signed Petersen graphs confirm Zaslavsky’s conjecture. We also computed the chromatic polynomials of all signed complete graphs with up to five vertices.

Keywords
signed graph, Petersen graph, complete graph, chromatic polynomial, zero-free chromatic polynomial
Mathematical Subject Classification 2010
Primary: 05C22
Secondary: 05A15, 05C15
Supplementary material

Sage code for computing chromatic polynomials of signed graphs

Milestones
Received: 18 April 2014
Revised: 18 December 2014
Accepted: 13 January 2015
Published: 28 September 2015

Communicated by Kenneth S. Berenhaut
Authors
Matthias Beck
Department of Mathematics
San Francisco State University
San Francisco, CA 94132
United States
Erika Meza
Department of Mathematics
Loyola Marymount University
Los Angeles, CA 90045
United States
Bryan Nevarez
Department of Mathematics
Queens College, CUNY
Flushing, NY 11367
United States
Alana Shine
Department of Computer Science
University of Southern California
Los Angeles, CA 90089
United States
Michael Young
Department of Mathematics
Iowa State University
Ames, IA 50011
United States