2000 | OriginalPaper | Buchkapitel
λ-Coloring of Graphs
verfasst von : Hans L. Bodlaender, Ton Kloks, Richard B. Tan, Jan van Leeuwen
Erschienen in: STACS 2000
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A λ-coloring of a graph G is an assignment of colors from the set 0, ..., λ to the vertices of a graph G such that vertices at distance at most two get different colors and adjacent vertices get colors which are at least two apart. The problem of finding λ-colorings with small or optimal λ arises in the context of radio frequency assignment. We show that the problems of finding the minimum λ for planar graphs, bipartite graphs, chordal graphs and split graphs are NP-Complete. We then give approximation algorithms for λ-coloring and compute upperbounds of the best possible λ for outerplanar graphs, planar graphs, graphs of treewidth k, permutation and split graphs. With the exception of the split graphs, all the above bounds for λ are linear in Δ, the maximum degree of the graph. For split graphs, we give a bound of λ ≤ Δ1.5+2Δ+2 and show that there are split graphs with λ = Ω(Δ1.5). Similar results are also given for variations of the λ-coloring problem.