Welsh-Powell opposition graphs
From MaRDI portal
We characterize a class of graphs for which the Welsh-Powell colouring heuristics results in an optimum colouring. We outline a polynomial-time recognition algorithm together with linear-time optimization algorithms for this class of graphs.
Recommendations
Cites work
- All variations on perfectly orderable graphs
- An upper bound for the chromatic number of a graph and its application to timetabling problems
- Four classes of perfectly orderable graphs
- scientific article; zbMATH DE number 3891425 (Why is no real title available?)
- scientific article; zbMATH DE number 3918092 (Why is no real title available?)
- On the semi-perfect elimination
Cited in
(6)- Some aspects of the semi-perfect elimination
- Recognition of some perfectly orderable graph classes
- On the complexity of distributed graph coloring with local minimality constraints
- Characterization and recognition of some opposition and coalition graph classes
- A simple nc recognition algorithm for welsh-powell opposition graphs
- An nc algorithm to recognize hhd-free graphs
This page was built for publication: Welsh-Powell opposition graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1115450)
