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.