{"id":2689,"date":"2016-02-16T16:44:27","date_gmt":"2016-02-16T15:44:27","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=2689"},"modified":"2022-12-03T22:59:01","modified_gmt":"2022-12-03T21:59:01","slug":"coloration-cliques-et-stables","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/click-and-stable-coloring\/","title":{"rendered":"Coloring, clicks and stables"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"2689\" class=\"elementor elementor-2689\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7717f12 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7717f12\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-1c80c33\" data-id=\"1c80c33\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ebeee03 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"ebeee03\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Graph theory<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-bed0043\" data-id=\"bed0043\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-152529e elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"152529e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-3a72af2\" data-id=\"3a72af2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-482fc6e elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"482fc6e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Coloration_de_graphe\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6bca73e1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6bca73e1\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-5886b16a\" data-id=\"5886b16a\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1347f53 elementor-widget elementor-widget-text-editor\" data-id=\"1347f53\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/click-and-stable-coloring\/#Coloration-de-graphe\" >Graph coloring<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/click-and-stable-coloring\/#Probleme-cliques\" >Problem: clicks<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/click-and-stable-coloring\/#Probleme-stables\" >Problem: stable<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/click-and-stable-coloring\/#Relation-entre-les-trois-problemes-et-heuristiques\" >Relationship between the three problems and heuristics<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/click-and-stable-coloring\/#Exemple\" >Example<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Coloration-de-graphe\"><\/span>Graph coloring<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">The graph coloring problem, for a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> G undirected, consists in assigning a color to each vertex in such a way that the same color is not assigned to two adjacent vertices.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>When the graph is planar, this amounts to the problem of coloring a geographical map. The problem of graph coloring arises in many practical areas such as pattern matching, <a href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/\">planning<\/a> sports, designing seating plans, reviewing timetables, scheduling taxis, and solving Sudoku.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">The minimum number of colors necessary to color the graph G is called the chromatic number of G, and is denoted by X (G).<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">The problem of finding the chromatic number of a graph is an Np-complete problem. The problem of coloring a graph with a limited number of colors - is it possible to color the graph with x colors, if so how? - is also an Np-complete problem.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>A planar graph is at most 4-chromatic.<\/p>\n<p>A chain is at most 2-chromatic.<\/p>\n<p>A cycle is at most 3-chromatic.<\/p>\n<p>A clique of size n is n-chromatic.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Example: A given set of tasks must be assigned to time intervals, each task requires only one interval. Tasks can be scheduled in any order, but task pairs can conflict in the sense that they cannot be assigned to the same time interval, for example because they both rely on a shared resource . The corresponding graph contains a vertex for each job and an edge for each pair of conflicting jobs. The chromatic number of the graphic is exactly the minimum required, the optimal time to complete all work without conflicts.<\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Probleme-cliques\"><\/span>Problem: clicks<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">Given an undirected graph G, a clique is a subset of vertices which are all connected in pairs by edges. In other words, it is a complete subgraph.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">Find a click <strong>w<\/strong> order <strong>k<\/strong> in a graph is an Np-complete problem.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>The following graph has a clique of order 5:<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image\"><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-2714 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/grapheclique-300x291.jpg\" alt=\"click\" width=\"300\" height=\"291\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/grapheclique-300x291.jpg 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/grapheclique.jpg 444w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Probleme-stables\"><\/span>Problem: stable<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">Given an undirected graph G, a stable is a subset of vertices which are not connected in pairs by edges. Finding a stable of order k amounts to finding a clique of order k in the inverse graph, that is to say that it has an edge if it does not exist in the original graph, and vice versa.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">Find a stable <strong>To<\/strong> of order k in a graph is an Np-complete problem.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-2723\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/280px-independent_set_graph-svg.png\" alt=\"stable\" width=\"280\" height=\"280\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/280px-independent_set_graph-svg.png 280w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/280px-independent_set_graph-svg-150x150.png 150w\" sizes=\"(max-width: 280px) 100vw, 280px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Relation-entre-les-trois-problemes-et-heuristiques\"><\/span>Relationship between the three problems and heuristics<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>We have the following three proposals:<\/p>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>a (G) = w (not G)<\/li>\n<li>w (G) = a (not G)<\/li>\n<li>X (G)&gt; = w (G)<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>A stable S of G is said to be maximal by inclusion if there is no stable S &#039;of G such that S is strictly contained in S&#039;. A clique K is maximal by inclusion if there are no cliques K &#039;of G such that K is strictly contained in K&#039;.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>By this definition, we deduce that a stable of maximum order is also a maximum stable by inclusion, the converse is not true. The classic heuristic for obtaining a large stable is to seek a maximal stable by inclusion.<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-2743\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/stable2.png\" alt=\"stable\" width=\"497\" height=\"209\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/stable2.png 497w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/stable2-300x126.png 300w\" sizes=\"(max-width: 497px) 100vw, 497px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>The Br\u00e9laz algorithm is a <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithm<\/a> greedy which allows to know a maximum limit of the chromatic number of a graph. Its principle is simple and iteratively proceeds.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<p style=\"text-align: justify;\">As long as there is an uncolored vertex, we choose the uncolored vertex with the highest number of neighbors colored with different colors. This vertex is then colored with the smallest possible color (the colors are sorted in an arbitrary ascending order). If all the existing colors are already used by a neighbor, we add a new color to our palette (adding a color with a higher value than all the other existing ones).<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>The notion of stable can also provide indications on the coloring of a graph. Indeed, we can assume that in a stable, all the vertices have the same color. Coloring in <strong>k<\/strong> colors amounts to finding a partition of the set of stable vertices in k.<\/p>\n<p><\/p>\n<p><\/p>\n<p>The Welsh and Powell algorithm is based on this proposition:<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<ol>\n<li style=\"text-align: justify;\">Order the vertices of the graph in decreasing order of their degree<\/li>\n<li style=\"text-align: justify;\">Going through the list in order, assign an unused color to the first uncolored vertex <strong>p<\/strong>, and assign this color to each next uncolored vertex such that it is not adjacent to the vertex <strong>p<\/strong>.<\/li>\n<li style=\"text-align: justify;\">Return to 2 if there are uncolored vertices in the list. Otherwise return the list.<\/li>\n<\/ol>\n<\/div>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Example<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6437\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku.png\" alt=\"sudoku graph coloring\" width=\"294\" height=\"282\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>To see the connection between Sudoku and graph coloring, we will first describe the Sudoku graph, which we will call for convenience S. Graph S has 81 vertices, each vertex representing a cell. When two cells cannot have the same number (either because they are in the same row, in the same column, or in the same box), we put an edge connecting the corresponding vertices of the Sudoku S graph. <\/p>\n<p>For example, since cells a3 and a7 are in the same row, there is an edge joining their corresponding vertices; there is also an edge connecting a1 and b3 (they are in the same box), and so on. Each vertex in the Sudoku graph has a 20 degree, and the graph has a total of 810 edges. S is too big to be drawn, but we can get an idea of the structure of S by looking at a partial drawing. The drawing shows the 81 vertices of S, but only two (a1 and e5) have their full set of incident edges.<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6438\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku2.png\" alt=\"sudoku graph coloring\" width=\"429\" height=\"441\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku2.png 429w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku2-292x300.png 292w\" sizes=\"(max-width: 429px) 100vw, 429px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>The second step in converting a Sudoku puzzle into a graph coloring problem is to assign colors to the numbers 1 through 9. This assignment is arbitrary and is not a priority order of colors as in the algorithm. gluttonous.<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6439\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku3.png\" alt=\"sudoku graph coloring\" width=\"348\" height=\"62\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku3.png 348w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku3-300x53.png 300w\" sizes=\"(max-width: 348px) 100vw, 348px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Once we have the Sudoku graph and an assignment of colors to the numbers 1 to 9, any Sudoku puzzle can be described by a Sudoku graph where some of the vertices are already colored (those corresponding to the data). To solve the Sudoku puzzle, all we have to do is color the rest of the vertices using the nine colors.<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6440\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku4.png\" alt=\"sudoku graph coloring\" width=\"425\" height=\"424\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku4.png 425w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku4-300x300.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku4-150x150.png 150w\" sizes=\"(max-width: 425px) 100vw, 425px\" \/><\/figure>\n<\/div>\n<p><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Graph theory Wiki home page Graph coloring The graph coloring problem, for an undirected graph G, consists in assigning a \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":2204,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-2689","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2689","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=2689"}],"version-history":[{"count":11,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2689\/revisions"}],"predecessor-version":[{"id":18432,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2689\/revisions\/18432"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2204"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=2689"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}