Problemas de coloração de grafos com poucos P4´s - Martins, Nicolas de Almeida (2013)
The coloring problems are among the most studied in the graph theory due to its great theoretical and practical importance. The L(2;1)-labeling problem, for instance, can be applied to the frequency assignment of transmission towers in order to decrease interference in transmissions. However most of the graph coloring problems are difficult to solve (NP-hard). In this thesis, we study the L(2;1)-coloring, the harmonious coloring and M-partition of graphs. Considering that the coloring problems addressed in this thesis are all NP-hard, we decided to study the restrictions of these problems to (q;q-4)-graphs, with q fixed. The solutions use the Primeval decomposition of these graphs. We also emphasize that this class contains the cographs and P₄-sparse graphs. The algorithms found in this way are called Fixed parameter tractable (FPT), because they run on polynomial time if we consider a certain parameter as a fixed value. Besides obtaining algorithms for several coloring problems restricted to (q;q-4)-graphs, with q fixed, we also evaluated Conjecture of Griggs-Yeh graphs with respect to P₄-Sparse and P₄-Laden graphs.