Algorithms for maximimum k-colorings and k-coverings of transitive graphs. (English) Zbl 0642.05021

Summary: 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.


05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Aharoni, Pacific J. Math. 118 pp 249– (1985) · Zbl 0569.05024
[2] Even, J. ACM 19 pp 400– (1972)
[3] Frank, J. Combinatorial Theory, Ser. B 29 pp 176– (1980)
[4] and , Flows in Networks. Princeton University Press, Princeton (1962).
[5] and , Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman, San Francisco (1978).
[6] Greene, J. Combinatorial Theory (A) 20 pp 69– (1976)
[7] Greene, J. Combinatorial Theory (A) 20 pp 41– (1976)
[8] Ordered Sets. In , Ed., Proc. of the NATO Advanced Study Institute held at Banff Canada, 1981, D. Reidel Publ. Co. (1982) 619–654.
[9] Hoffman, J. Combinatorial Theory (A) 34 pp 102– (1983)
[10] Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York (1976). · Zbl 0413.90040
[11] Linial, J. Combinatorial Theory, (A) 30 pp 331– (1981)
[12] Pnueli, Can. J. Math. 23 pp 160– (1971) · Zbl 0204.24604
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.