Optimality of DSatur algorithm on chordal graphs

DOI10.1016/J.ORL.2024.107185MaRDI QIDQ6988282zbMATH OpenFDO

Authors Majid Zohrehbandian, M. Maghasedi, Flavia Bonomo

Publication date 5 May 2025

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.ORL.2024.107185

zbMATH Keywords

chordal graphsDSatur algorithmvertex coloring problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85)

Cites work

• A DSATUR-based algorithm for the equitable coloring problem
• A new \textsf{DSATUR}-based algorithm for exact vertex coloring
• Algorithmic graph theory and perfect graphs
• An improved DSATUR-based branch-and-bound algorithm for the vertex coloring problem
• Chromatic Scheduling and the Chromatic Number Problem
• Guide to graph colouring. Algorithms and applications
• scientific article; zbMATH DE number 1944138 (Why is no real title available?)
• scientific article; zbMATH DE number 956855 (Why is no real title available?)
• Incidence matrices and interval graphs
• New methods to color the vertices of a graph
• On rigid circuit graphs
• Reducibility among combinatorial problems
• The smallest hard-to-color graph for algorithm DSATUR
• Triangulated graphs and the elimination process

Cited in

(1)

• Design and implementation of a graph-coloring algorithm for optimizing flight-level allocation in air traffic management in Iran

This page was built for publication: Optimality of DSatur algorithm on chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6988282)