Premium
Algorithms for maximum k ‐colorings and k ‐coverings of transitive graphs
Author(s) -
Gavril Fǎnicǎ
Publication year - 1987
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.3230170407
Subject(s) - combinatorics , mathematics , transitive relation , disjoint sets , graph , integer (computer science) , discrete mathematics , computer science , programming language
Consider a graph G and a positive integer k . The maximum k‐coloring problem is to color a maximum number of vertices using k colors, such that no two adjacent vertices have the same color. The maximum k‐covering problem is to find k disjoint cliques covering a maximum number of vertices. The present paper contains polynomial time algorithms for finding maximum k ‐colorings and maximum k ‐coverings of transitive graphs.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom