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

Gavril, Fănică

Networks 17, No. 4, 465-470 (1987).

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.

MSC:

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

Keywords:

maximum k-coloring problem; maximum k-covering problem; polynomial time algorithms

References:

[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