Abstract | ||
---|---|---|
An L(2,1)-coloring of a graph G is a coloring of G's vertices with integers in {0,1,...,k} so that adjacent vertices' colors differ by at least two and colors of distance-two vertices differ. We refer to an L(2,1)-coloring as a coloring. The span λ(G) of G is the smallest k for which G has a coloring, a span coloring is a coloring whose greatest color is λ(G), and the hole index ρ(G) of G is the minimum number of colors in {0, 1,...,λ(G)} not used in a span coloring. We say that G is full-colorable if ρ(G) = 0. More generally, a coloring of G is a no-hole coloring if it uses all colors between 0 and its maximum color. Both colorings and no-hole colorings were motivated by channel assignment problems. We define the no-hole span µ(G) of G as ∞ if G has no no-hole coloring; otherwise µ(G) is the minimum k for which G has a no-hole coloring using colors in {0, 1,....,k}.Let n denote the number of vertices of G, and let Δ be the maximum degree of vertices of G. Prior work shows that all non-star trees with Δ ≥ 3 are full-colorable, all graphs G with n=λ(G)+ 1 are full-colorable, µ(G) ≤ λ(G)+ ρ(G) if G is not full-colorable and n ≥ λ(G) + 2, and G has a no-hole coloring if and only if n ≥ λ(G) + 1. We prove two extremal results for colorings. First, for every m ≥ 1 there is a G with ρ(G) = m and µ(G)=λ(G) + m. Second, for every m ≥ 2 there is a connected G with λ(G) = 2m, n = λ(G) + 2 and ρ(G) = m. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1016/S0166-218X(03)00329-9 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
indexation,maximum degree | Journal | 130 |
Issue | ISSN | Citations |
3 | Discrete Applied Mathematics | 13 |
PageRank | References | Authors |
0.88 | 8 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Peter C. Fishburn | 1 | 740 | 136.75 |
Fred S. Roberts | 2 | 527 | 85.71 |