𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Algorithms for maximum k-colorings and k-coverings of transitive graphs

✍ Scribed by Fǎnicǎ Gavril

Publisher
John Wiley and Sons
Year
1987
Tongue
English
Weight
356 KB
Volume
17
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Maximum number of colorings of (2k, k2)-
Maximum number of colorings of (2k, k2)-graphs
✍ Felix Lazebnik; Oleg Pikhurko; Andrew Woldar 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

## Abstract Let ${\cal F}\_{{2}{k},{k}^{2}}$ consist of all simple graphs on 2__k__ vertices and ${k}^{2}$ edges. For a simple graph __G__ and a positive integer $\lambda$, let ${P}\_{G}(\lambda)$ denote the number of proper vertex colorings of __G__ in at most $\lambda$ colors, and let $f(2k, k^{2

An algorithm for construction of a k-con
An algorithm for construction of a k-connected graph with minimum number of edges and quasiminimal diameter
✍ Ulrich Schumacher 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 470 KB

Two fundamental considerations in the design of a communication network are reliability and maximum transmission delay. In this paper we give an algorithm for construction of an undirected graph with n vertices in which there are k node-disjoint paths between any two nodes. The generated graphs will

A covering construction for packing disj
A covering construction for packing disjoint copies of the Hoffman-Singleton graph into K50
✍ Jana Ŝiagiová; Mariusz Meszka 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

## Abstract In this note we show how coverings induced by voltage assignments can be used to produce packings of disjoint copies of the Hoffman‐Singleton graph into __K__~50~. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 408–412, 2003; Published online in Wiley InterScience (www.interscience

Vertex decompositions of sparse graphs i
Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
✍ O. V. Borodin; A. O. Ivanova; M. Montassier; P. Ochem; A. Raspaud 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A graph __G__ is (__k__,0)‐colorable if its vertices can be partitioned into subsets __V__~1~ and __V__~2~ such that in __G__[__V__~1~] every vertex has degree at most __k__, while __G__[__V__~2~] is edgeless. For every integer __k__⩾0, we prove that every graph with the maximum average