Graph coloring problem

Planar graph coloring problem using Backtracking algorithm

1. Mrs.G.Chandraprabha,M.Sc.,M.Phil.,
Assistant Professor
Department of IT
V.V.Vanniaperumal College for Women
Virudhunagar
Graph Coloring problem
Using Backtracking

2. GraphColoringisanassignmentofcolors(orany
distinctmarks)totheverticesofagraph.Strictly
speaking,acoloringisapropercoloringifnotwo
adjacentverticeshavethesamecolor.SGVf )(:

3. Definition:Agraphisplanarifitcanbedrawninaplane
withoutedge-crossings.
Thefourcolortheorem:Foreveryplanargraph,the
chromaticnumberis≤4.

4. Thefourcolortheoremstatesthatanyplanarmapcan
becoloredwithatmostfourcolors.
Ingraphterminology,thismeansthatusingatmost
fourcolors,anyplanargraphcanhaveitsnodescolored
suchthatnotwoadjacentnodeshavethesamecolor.
Four-colorconjecture–FrancisGuthrie,1852(F.G.)
Manyincompleteproofs(Kempe).
5-colortheoremprovedin1890(Heawood)
4-colortheoremfinallyprovedin1977(Appel,Haken)
◦Firstmajorcomputer-basedproof

5. Avertexcoloringisanassignmentoflabelsorcolors
toeachvertexofagraphsuchthatnoedgeconnects
twoidenticallycoloredvertices

6. Similartovertexcoloring,exceptedgesarecolor.
Adjacentedgeshavedifferentcolors.

7. Everyedge-coloringproblemcanbetransformedintoa
vertex-coloringproblem
ColoringtheedgesofgraphGisthesameascoloring
theverticesinL(G)
Noteveryvertex-coloringproblemcanbetransformed
toanedge-coloringproblem
Everygraphhasalinegraph,butnoteverygraphisa
linegraphofsomeothergraph

8. K-Coloring
◦Ak-coloringofagraphGisamappingofV(G)onto
theintegers1..ksuchthatadjacentverticesmapinto
differentintegers.
◦Ak-coloringpartitionsV(G)intokdisjointsubsets
suchthatverticesfromdifferentsubsetshave
differentcolors.

9. K-colorable
◦AgraphGisk-colorableifithasak-coloring.
ChromaticNumber
◦ThesmallestintegerkforwhichGisk-colorableis
calledthechromaticnumberofG,isdenotedbythe
χ(G).

10. Theideaistoassigncolorsonebyonetodifferent
vertices,startingfromthevertex0.Beforeassigninga
color,wecheckforsafetybyconsideringalready
assignedcolorstotheadjacentvertices.
Ifwefindacolorassignmentwhichissafe,wemark
thecolorassignmentaspartofsolution.
Ifwedonotafindcolorduetoclashesthenwe
backtrackandreturnfalse.
Backtracking Algorithm

11. NP:theclassofdecisionproblemsthataresolvablein
polynomialtimeonanondeterministicmachine(orwitha
nondeterministicalgorithm)
(Adeterministiccomputeriswhatweknow)
Anondeterministiccomputerisonethatcan“guess”theright
answerorsolutionthinkofanondeterministiccomputerasa
parallelmachinethatcanfreelyspawnaninfinitenumberof
processes
ThusNPcanalsobethoughtofastheclassofproblems
whosesolutionscanbeverifiedinpolynomialtime
NotethatNPstandsfor“NondeterministicPolynomial-time”

12. FractionalKnapsack
Sorting
Others?
◦GraphColoring
◦Satisfiability(SAT)
theproblemofdecidingwhetheragiven
Booleanformulaissatisfiable.

13. Manyproblemscanbeformulatedasagraphcoloring
problemincludingTimeTabling,Scheduling,Register
Allocation,ChannelAssignment.
Alotofresearchhasbeendoneinthisareasomuchis
alreadyknownabouttheproblemspace.

14. Thank You