On edge orienting methods for graph coloring

DOI10.1007/S10878-006-9019-3MaRDI QIDQ2385485zbMATH OpenOpenAlexFDO

Authors Bernard Gendron, Alain Hertz, Patrick St-Louis

Publication date 12 October 2007

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-006-9019-3

zbMATH Keywords

Local searchGraph coloringEdge orienting

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Orientable edge colorings of graphs
• scientific article; zbMATH DE number 68344
• Graph edge coloring: a survey
• Edge-Coloring Problems for Graphs.
• On resolving edge colorings in graphs
• scientific article; zbMATH DE number 1560509
• A polyhedral approach to edge coloring
• scientific article; zbMATH DE number 4008416
• Oriented graph coloring
• Colorings and orientations of graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1062113 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• A Column Generation Approach for Graph Coloring
• A survey of local search methods for graph coloring
• Chromatic Scheduling and the Chromatic Number Problem
• Finding the chromatic number by means of critical graphs
• Job Shop Scheduling by Simulated Annealing
• Nombre chromatique et plus longs chemins d'un graphe
• Two novel evolutionary formulations of the graph coloring problem

Cited in

(6)

• Parameterized mixed graph coloring
• Orientable edge colorings of graphs
• A wide-ranging computational comparison of high-performance graph colouring algorithms
• Very Large-Scale Neighborhood Search: Overview and Case Studies on Coloring Problems
• Variable space search for graph coloring
• Corrigendum to ``Variable space search for graph coloring [Discrete Appl. Math. 156, No.\,13, 2551--2560 (2008; Zbl 1213.05085)]

Describes a project that uses

Uses Software

• Tabu search
• DIMACS

This page was built for publication: On edge orienting methods for graph coloring

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