Algorithms for maximum k‐colorings and k‐coverings of transitive graphs
Author:
Abstract
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.Keywords
This publication has 9 references indexed in Scilit:
- Path partitions and packs of acyclic digraphsPacific Journal of Mathematics, 1985
- Extending Greene's theorem to directed graphsJournal of Combinatorial Theory, Series A, 1983
- Extending the Greene-Kleitman theorem to directed graphsJournal of Combinatorial Theory, Series A, 1981
- On chain and antichain families of a partially ordered setJournal of Combinatorial Theory, Series B, 1980
- Some partitions associated with a partially ordered setJournal of Combinatorial Theory, Series A, 1976
- The structure of sperner k-familiesJournal of Combinatorial Theory, Series A, 1976
- Permutation Graphs and Transitive GraphsJournal of the ACM, 1972
- Transitive Orientation of Graphs and Identification of Permutation GraphsCanadian Journal of Mathematics, 1971
- Flows in Networks1963