Limites superiores para o número cromático L(3,2,1) de classes de grafos com grau máximo três

Abstract

Given a graph G, a function f :V(G) → {0,1,2,...,k} is said to be an L(3,2,1)-labelling of G if, for each u,v ∈V(G): when d(u,v) = 1, then |f(u)− f(v)| ≥ 3; when d(u,v) = 2, then | f (u) − f(v)| ≥ 2; and when d(u,v) = 3, then |f(u)− f(v)| ≥ 1. The span of an L(3,2,1)labelling f is the largest label assigned by f to a node of G. An L(3,2,1)-labelling is said to be optimal when it has the minimum possible span, and the span of such a labeling is called the L(3,2,1) chromatic number, and denoted by λ3,2,1(G). The class of cubic graphs is of interest in Graph Theory and Algorithms because many decision problems in arbitrary graphs are NPcomplete and remain NP-Complete even when constrained to cubic graphs. A graph is said to be subcubic when its maximum degree is equal to 3. Another class of graphs relevant to Graph Theory is the class of snark graphs. A snark graph is a bridgeless cubic graph that does not have a proper edge coloring with 3 colors. In this work, we show a tighter upper bound for the L(3,2,1) chromatic number of a subclass of subcubic graphs, such that there are no adjacent nodes with maximum degree such that any two nodes with degree equal to 3 are at distance at least 4 from each other, improving upon previous results in the literature. We also show tighter upper bounds for the L(3,2,1) chromatic number for the following infinite families of snarks: generalized Blanuša snarks, Loupekine snarks, and Flower snarks.