Welsh-Powell opposition graphs (Q1115450): Difference between revisions

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.

0 references

zbMATH Keywords

Welsh-Powell colouring heuristics

0 references

optimum colouring

0 references

recognition algorithm

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0020-0190(89)90107-5

0 references

cites work

Q3347930

0 references

Four classes of perfectly orderable graphs

0 references

On the semi-perfect elimination

0 references

All variations on perfectly orderable graphs

0 references

Q3693257

0 references

An upper bound for the chromatic number of a graph and its application to timetabling problems

0 references

Identifiers

zbMATH Open document ID

0664.05022

0 references

DOI

10.1016/0020-0190(89)90107-5

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1115450

@@ Property / cites work @@
+Q3347930
@@ Property / cites work: Q3347930 / rank @@
+Normal rank
@@ Property / cites work @@
+Four classes of perfectly orderable graphs
@@ Property / cites work: Four classes of perfectly orderable graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the semi-perfect elimination
@@ Property / cites work: On the semi-perfect elimination / rank @@
+Normal rank
@@ Property / cites work @@
+All variations on perfectly orderable graphs
@@ Property / cites work: All variations on perfectly orderable graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3693257
@@ Property / cites work: Q3693257 / rank @@
+Normal rank
@@ Property / cites work @@
+An upper bound for the chromatic number of a graph and its application to timetabling problems
+Normal rank