Premium
The chromatic reduction problem
Author(s) -
Brown J. R.
Publication year - 1973
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230030407
Subject(s) - chromatic scale , reduction (mathematics) , graph , critical graph , combinatorics , mathematics , graph reduction , set (abstract data type) , discrete mathematics , computer science , theoretical computer science , graph power , line graph , functional programming , geometry , programming language
The chromatic reduction problem is to find the minimum number of vertices that have to be eliminated from a graph so that the resultant subgraph has a chromatic number of k. When k = 1, the chromatic reduction problem reduces to finding the maximum internally stable set of a graph. An algorithm is developed for the chromatic reduction problem and computational experience is given.