L(2, 1)-colorações: algoritmos e limites superiores em classes de grafos
Resumo
O problema da L(2, 1)-coloração é uma variação do problema da coloração de vértices de um grafo, onde vértices adjacentes recebem cores (representadas por números naturais) com diferença de pelo menos dois e vértices não adjacentes, mas que tenham um vizinho em comum, recebem cores diferentes. O objetivo é minimizar o span, ou seja, a maior cor utilizada. Esta dissertação, além de conter uma coletânea detalhada dos principais resultados já conhecidos, também apresenta um algoritmo linear para a classe dos grafos P4-tidy, o estabelecimento de limites superiores do span em grafos fracamente cordais, linha e bipartidos cordais, a melhoria dos limites superiores conhecidos do span em grafos split, permutação e cografos, entre outros.Referências
Araki, T. (2009). Labeling bipartite permutation graphs with a condition at distance two. Discrete Applied Mathematics, 157(8):1677–1686.
Balakrishnan, H. e Deo, N. (2003). Parallel algorithm for radiocoloring a graph. Congressus Numerantium, 160(1):192–205.
Bodlaender, H. L., Kloks, T., Tan, R. B. e van Leeuwen, J. (2004). Approximations for λ-coloring of graphs. The Computer Journal, 47:193–204.
Calamoneri, T. (2009). The L(h, k)-labelling problem: A survey and annotated bibliography. [link].
Calamoneri, T. e Petreschi, R. (2001). λ-coloring of regular tiling. Electronic Notes in Discrete Mathematics, 8:18–21.
Calamoneri, T. e Petreschi, R. (2006). λ-coloring matrogenic graphs. Discrete Applied Mathematics, 154(17):2445 – 2457.
Chang, G. J. e Kuo, D. (1996). The L(2, 1)-labeling problem on graphs. SIAM Journal on Discrete Mathematics, 9(2):309–316.
Fiala, J., Kloks, T. e Kratochvíl, J. (2001). Fixed-parameter complexity of λ-labelings. Discrete Applied Mathematics, 113(1):59–72.
Gonçalves, D. (2005). On the L(p, 1)-labeling of graphs. Proceedings of European conference on Combinatorics Graph Theory and Applications (EuroComb 05), 5(9):81–86.
Griggs, J. R. e Yeh, R. K. (1992). Labelling graphs with a condition at distance 2. SIAM Journal on Discrete Mathematics, 5(4):586–595.
Hasunuma, T., Ishii, T., Ono, H. e Uno, Y. (2009). A linear algorithm for L(2, 1)-labeling of trees. pre-print.
Havet, F., Reed, B. e Sereni, J. (2008). L(2, 1)-labelling of graphs. In SODA 2008: Proceedings of annual ACM-SIAM symposium on Discrete algorithms, pages 621–630. Society for Industrial and Applied Mathematics.
Kang, J. (2004). L(2, 1)-labelling of 3-regular hamiltonian graphs. Ph.D. thesis, University of Illinois.
Kratochvíl, J., Kratsch, D. e Liedloff, M. (2007). Exact algorithms forL(2, 1)-labelings of graphs. Proceedings of 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS 07), 4(1):513–524.
Král, D. (2005a). Coloring powers of chordal graphs. SIAM Journal on Discrete Mathematics, 18(3):451–461.
Král, D. (2005b). An exact algorithm for the channel assignment problem. Discrete Applied Mathematics, 145(1):326–331.
Král, D. e Skrekovski, R. (2003). A theorem about the channel assignment problem. SIAM Journal on Discrete Mathematics, 16(1):426–437.
Sakai, D. (1994). Labeling chordal graphs: distance two condition. SIAM Journal on Discrete Mathematics, 7:133–140.
Balakrishnan, H. e Deo, N. (2003). Parallel algorithm for radiocoloring a graph. Congressus Numerantium, 160(1):192–205.
Bodlaender, H. L., Kloks, T., Tan, R. B. e van Leeuwen, J. (2004). Approximations for λ-coloring of graphs. The Computer Journal, 47:193–204.
Calamoneri, T. (2009). The L(h, k)-labelling problem: A survey and annotated bibliography. [link].
Calamoneri, T. e Petreschi, R. (2001). λ-coloring of regular tiling. Electronic Notes in Discrete Mathematics, 8:18–21.
Calamoneri, T. e Petreschi, R. (2006). λ-coloring matrogenic graphs. Discrete Applied Mathematics, 154(17):2445 – 2457.
Chang, G. J. e Kuo, D. (1996). The L(2, 1)-labeling problem on graphs. SIAM Journal on Discrete Mathematics, 9(2):309–316.
Fiala, J., Kloks, T. e Kratochvíl, J. (2001). Fixed-parameter complexity of λ-labelings. Discrete Applied Mathematics, 113(1):59–72.
Gonçalves, D. (2005). On the L(p, 1)-labeling of graphs. Proceedings of European conference on Combinatorics Graph Theory and Applications (EuroComb 05), 5(9):81–86.
Griggs, J. R. e Yeh, R. K. (1992). Labelling graphs with a condition at distance 2. SIAM Journal on Discrete Mathematics, 5(4):586–595.
Hasunuma, T., Ishii, T., Ono, H. e Uno, Y. (2009). A linear algorithm for L(2, 1)-labeling of trees. pre-print.
Havet, F., Reed, B. e Sereni, J. (2008). L(2, 1)-labelling of graphs. In SODA 2008: Proceedings of annual ACM-SIAM symposium on Discrete algorithms, pages 621–630. Society for Industrial and Applied Mathematics.
Kang, J. (2004). L(2, 1)-labelling of 3-regular hamiltonian graphs. Ph.D. thesis, University of Illinois.
Kratochvíl, J., Kratsch, D. e Liedloff, M. (2007). Exact algorithms forL(2, 1)-labelings of graphs. Proceedings of 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS 07), 4(1):513–524.
Král, D. (2005a). Coloring powers of chordal graphs. SIAM Journal on Discrete Mathematics, 18(3):451–461.
Král, D. (2005b). An exact algorithm for the channel assignment problem. Discrete Applied Mathematics, 145(1):326–331.
Král, D. e Skrekovski, R. (2003). A theorem about the channel assignment problem. SIAM Journal on Discrete Mathematics, 16(1):426–437.
Sakai, D. (1994). Labeling chordal graphs: distance two condition. SIAM Journal on Discrete Mathematics, 7:133–140.
Publicado
20/07/2010
Como Citar
CERIOLI, Márcia R.; POSNER, Daniel F. D..
L(2, 1)-colorações: algoritmos e limites superiores em classes de grafos. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 23. , 2010, Belo Horizonte/MG.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2010
.
p. 25-32.
ISSN 2763-8820.
