Skip to content

A program to demostrate if the Petersen graph is n-colorable graph , and the relations of the colorable problem with the clique problem.

License

Notifications You must be signed in to change notification settings

Jeffresh/The-Petersen-Graph

Repository files navigation

The-Petersen-Graph

Abstract

A program to demostrate if the Petersen graph is n-colorable graph , and the relations of the colorable problem with the clique problem. To do that i will use a (polynomial) reduction of this problem to SAT problem. So, with this application, you can get the necessary proof to know about why the chromatic number of the Petersen graph is three and the relation of the chromatic number and the clique number, which is two, of this graph.

Introduction

To Start, I will develop a data structure to represent the graph, using a adjacency list in the programming language C++, so its necessary have a deep knowledge of this language to understand the logic of the attached files that encode the logic of the problem.

Its necessary too, learn about the DIMACSformat, because we will use a file in this format to feed the PicoSAT program to know if our graph is n-colorable. So its essential to know about this two topics if you want to get a deep understanding of the way that it works and to manipulate yourself the codes and to do your own experiments.

About

A program to demostrate if the Petersen graph is n-colorable graph , and the relations of the colorable problem with the clique problem.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

 
 
 

Languages