# A conditional greedy algorithm for edge-coloring

Source: [A conditional greedy algorithm for edge-coloring](<https://www.sota2.com/research/paper/68fa53ee1e209131ce9875e5>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T12:43:22.346Z

Authors: Mark K. Goldberg

Published: 2017-06-14T13:23:24.000Z

## Abstract

We present a novel algorithm for edge-coloring of multigraphs. The correctness of this algorithm for multigraphs with $\\chi' \> \\Delta +1$ ($\\chi'$ is the chromatic edge number and $\\Delta$ is the maximum vertex degree) would prove a long standing conjecture in edge-coloring of multigraphs.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1706.04476>)

[PDF](<https://arxiv.org/pdf/1706.04476.pdf>)
