{"id":2873,"date":"2025-04-07T10:44:49","date_gmt":"2025-04-07T13:44:49","guid":{"rendered":"https:\/\/icc.fcen.uba.ar\/?p=2873"},"modified":"2025-04-07T10:44:49","modified_gmt":"2025-04-07T13:44:49","slug":"optimality-of-dsatur-algorithm-on-chordal-graphs","status":"publish","type":"post","link":"https:\/\/icc.fcen.uba.ar\/en\/optimality-of-dsatur-algorithm-on-chordal-graphs\/","title":{"rendered":"Optimality of DSatur algorithm on chordal graphs"},"content":{"rendered":"<div class=\"fusion-fullwidth fullwidth-box fusion-builder-row-1 fusion-flex-container has-pattern-background has-mask-background nonhundred-percent-fullwidth non-hundred-percent-height-scrolling\" style=\"--awb-border-radius-top-left:0px;--awb-border-radius-top-right:0px;--awb-border-radius-bottom-right:0px;--awb-border-radius-bottom-left:0px;--awb-flex-wrap:wrap;\" ><div class=\"fusion-builder-row fusion-row fusion-flex-align-items-flex-start fusion-flex-content-wrap\" style=\"max-width:1144px;margin-left: calc(-4% \/ 2 );margin-right: calc(-4% \/ 2 );\"><div class=\"fusion-layout-column fusion_builder_column fusion-builder-column-0 fusion_builder_column_1_1 1_1 fusion-flex-column\" style=\"--awb-bg-size:cover;--awb-width-large:100%;--awb-margin-top-large:0px;--awb-spacing-right-large:1.92%;--awb-margin-bottom-large:20px;--awb-spacing-left-large:1.92%;--awb-width-medium:100%;--awb-order-medium:0;--awb-spacing-right-medium:1.92%;--awb-spacing-left-medium:1.92%;--awb-width-small:100%;--awb-order-small:0;--awb-spacing-right-small:1.92%;--awb-spacing-left-small:1.92%;\"><div class=\"fusion-column-wrapper fusion-column-has-shadow fusion-flex-justify-content-flex-start fusion-content-layout-column\"><div class=\"fusion-text fusion-text-1\"><p>Authors: N. Yekezare; M. Zohrehbandian; M. Maghasedi and F. Bonomo-Braberman.<\/p>\n<p>Abstract:<br \/>\nDSatur is a widely-used heuristic algorithm for graph coloring, proposed by Daniel Br\u00e9laz in 1979. It is based on the greedy coloring approach, but selecting the next vertex to be colored from those that maximize the number of colors already used by their neighbors. Though not always optimal, this algorithm is known to be optimal on certain families, like cycles or bipartite graphs. In this paper, we prove the optimality of DSatur on chordal graphs, a superclass of interval graphs.<\/p>\n<p>More information:<br \/>\n<a href=\"https:\/\/doi.org\/10.1016\/j.orl.2024.107185\" target=\"_blank\" rel=\"noopener\">https:\/\/doi.org\/10.1016\/j.orl.2024.107185<\/a><\/p>\n<\/div><\/div><\/div><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":9,"featured_media":2874,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[98],"tags":[],"class_list":["post-2873","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-papers"],"_links":{"self":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2873","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/users\/9"}],"replies":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/comments?post=2873"}],"version-history":[{"count":1,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2873\/revisions"}],"predecessor-version":[{"id":2875,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2873\/revisions\/2875"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media\/2874"}],"wp:attachment":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media?parent=2873"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/categories?post=2873"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/tags?post=2873"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}