Welsh-Powell opposition graphs

DOI10.1016/0020-0190(89)90107-5zbMath0664.05022OpenAlexW2012304296MaRDI QIDQ1115450

S. H. Smith

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90107-5

zbMATH Keywords

recognition algorithmoptimum colouringWelsh-Powell colouring heuristics

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (6)

A simple nc recognition algorithm for welsh-powell opposition graphs ⋮ Characterization and recognition of some opposition and coalition graph classes ⋮ An nc algorithm to recognize hhd-free graphs ⋮ Some aspects of the semi-perfect elimination ⋮ On the complexity of distributed graph coloring with local minimality constraints ⋮ Recognition of some perfectly orderable graph classes

Cites Work

• All variations on perfectly orderable graphs
• On the semi-perfect elimination
• Four classes of perfectly orderable graphs
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Unnamed Item
• Unnamed Item

This page was built for publication: Welsh-Powell opposition graphs