Packing colorings of subcubic outerplanar graphs
- PDF / 586,345 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 190 Views
Aequationes Mathematicae
Packing colorings of subcubic outerplanar graphs Boˇ stjan Breˇ sar , Nicolas Gastineau, and Olivier Togni
Abstract. Given a graph G and a nondecreasing sequence S = (s1 , . . . , sk ) of positive integers, the mapping c : V (G) −→ {1, . . . , k} is called an S-packing coloring of G if for any two distinct vertices x and y in c−1 (i), the distance between x and y is greater than si . The smallest integer k such that there exists a (1, 2, . . . , k)-packing coloring of a graph G is called the packing chromatic number of G, denoted χρ (G). The question of boundedness of the packing chromatic number in the class of subcubic (planar) graphs was investigated in several earlier papers; recently it was established that the invariant is unbounded in the class of all subcubic graphs. In this paper, we prove that the packing chromatic number of any 2connected bipartite subcubic outerplanar graph is bounded by 7. Furthermore, we prove that every subcubic triangle-free outerplanar graph has a (1, 2, 2, 2)-packing coloring, and that there exists a subcubic outerplanar graph with a triangle that does not admit a (1, 2, 2, 2)packing coloring. In addition, there exists a subcubic triangle-free outerplanar graph that does not admit a (1, 2, 2, 3)-packing coloring. A similar dichotomy is shown for bipartite outerplanar graphs: every such graph admits an S-packing coloring for S = (1, 3, . . . , 3), where 3 appears Δ times (Δ being the maximum degree of vertices), and this property does not hold if one of the integers 3 is replaced by 4 in the sequence S. Mathematics Subject Classification. 05C15, 05C12, 05C70. Keywords. Outerplanar graph, Packing chromatic number, Cubic graph, Coloring, Packing.
1. Introduction The S-packing chromatic number was introduced a decade ago in [17] with motivation coming from the frequency assignment problem. Roughly the idea of the concept is to generalize the classical coloring by involving the distance between vertices and allowing larger color values only for vertices that are more distant. Nevertheless, the problem has attracted the attention of many discrete mathematicians as it brings appealing combinatorial and computational challenges. Given a graph G and a positive integer d, a set A ⊆ V (G) is a d-packing in G if for any two distinct vertices x, y ∈ A the distance between x and y in
B. Breˇ sar et al.
AEM
G is greater than d. For a nondecreasing sequence S = (s1 , . . . , sk ) of positive integers, the mapping c : V (G) −→ {1, . . . , k} is an S-packing coloring of G if for every i ∈ [k] the set c−1 (i) is an si -packing. If there exists an S-packing coloring of G, we say that G is S-packing colorable. If the sequence is S = [k] for some positive integer k, we omit S in the definition, and say that G is packing colorable (as usual, we let [k] = {1, . . . , k}). The smallest integer k such that G is packing colorable is the packing chromatic number of G, denoted χρ (G). When we say that the packing coloring condition holds for a set A ⊆ V (G) we mean that each set
Data Loading...
