Problem 2461. Graph Algorithms - 2 : Chromatic Number

Created by rifat

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Chromatic number of a graph is the minimum number of distinct colors required to color all the vertices of the graph such that no two adjacent vertices (vertices that are connected by an edge) have same color. Adjacency matrix of a graph is given. Determine its chromatic number.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

38 Solutions
8 Solvers

Last Solution submitted on Apr 21, 2020

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Tim on 24 Jul 2014

Coloring [0 1 0 1 1 0 2] seems to work for test case 2, giving it a chromatic number of 3 rather than 4.

rifat on 25 Jul 2014

yes.. corrected. Thanks for pointing it out :-)

Problem Recent Solvers8

Problem Tags

graph theory

Problem 2461. Graph Algorithms - 2 : Chromatic Number

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author44

Problem Tags

Problem 2461. Graph Algorithms - 2 : Chromatic Number

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author44

Problem Tags

Players