Galáxias como backbone em colorações backbone
Resumo
Dados um inteiro q ≥ 2, um grafo simples G e um subgrafo gerador H, o número cromático (circular) q-backbone, denotado por BBCq(G, H) (resp. CBCq(G, H)), é o menor inteiro k tal que G tem uma k-coloração própria satisfazendo que se uv ∈ E(H), então |f(u) − f(v)| ≥ q (resp. k − q ≥ |f(u) − f(v)| ≥ q). Neste trabalho, mostramos que para grafo G planar e M um emparelhamento, então CBCq (G, M) ≤ q + 5, para q ∈ {2, 3}, sem usar o Teorema das Quatro Cores. Além disso, nós corrigimos um lema apresentado em Havet, King, Liedloff & Todinca (2014).
Palavras-chave:
limitantes, emparelhamento, coloração circular backbone
Referências
C. Araujo, J. Araujo, A. Silva, and A. Cezar, Backbone coloring of graphs with galaxy backbones, Electronic Notes in Theoretical Computer 346 (2019), 43–64.
H. Broersma, F. V. Fomin, P. A. Golovach, and G. J. Woeginger, Backbone colorings for networks, International Workshop on Graph-Theoretic Concepts in Computer Science, 2003, pp. 131–142.
H. Broersma, F. V. Fomin, G. J. Woeginger, and P. A. Golovach, Backbone colorings for graphs: tree and path backbones, Journal of Graph Theory 55 (2007), no. 2, 137–152.
H. Broersma, J. Fujisawa, L. Marchal, D. Paulusma, A. N. M. Salman, and K. Yoshimoto, λ-backbone colorings along pairwise disjoint stars and matchings, Discrete Mathematics 309 (2009), no. 18, 5596– 5609. Combinatorics 2006, A Meeting in Celebration of Pavol Hell’s 60th Birthday (May 1–5, 2006).
H. Broersma, J. Fujisawa, and K. Yoshimoto, Backbone colorings along perfect matchings, Memorandum, University of Twente, Department of Applied Mathematics, 2003 (English).
M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of np-completeness (series of books in the mathematical sciences), First Edition, W. H. Freeman, 1979.
W. K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE 68 (1980), no. 12, 1497–1514.
F. Havet, A. D. King, M. Liedloff, and I. Todinca, (circular) backbone colouring: Forest backbones in planar graphs, Discrete Applied Mathematics 169 (2014), 119–134.
D. B. West, Introduction to graph theory, 2nd ed., Prentice Hall, 2001.
H. Broersma, F. V. Fomin, P. A. Golovach, and G. J. Woeginger, Backbone colorings for networks, International Workshop on Graph-Theoretic Concepts in Computer Science, 2003, pp. 131–142.
H. Broersma, F. V. Fomin, G. J. Woeginger, and P. A. Golovach, Backbone colorings for graphs: tree and path backbones, Journal of Graph Theory 55 (2007), no. 2, 137–152.
H. Broersma, J. Fujisawa, L. Marchal, D. Paulusma, A. N. M. Salman, and K. Yoshimoto, λ-backbone colorings along pairwise disjoint stars and matchings, Discrete Mathematics 309 (2009), no. 18, 5596– 5609. Combinatorics 2006, A Meeting in Celebration of Pavol Hell’s 60th Birthday (May 1–5, 2006).
H. Broersma, J. Fujisawa, and K. Yoshimoto, Backbone colorings along perfect matchings, Memorandum, University of Twente, Department of Applied Mathematics, 2003 (English).
M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of np-completeness (series of books in the mathematical sciences), First Edition, W. H. Freeman, 1979.
W. K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE 68 (1980), no. 12, 1497–1514.
F. Havet, A. D. King, M. Liedloff, and I. Todinca, (circular) backbone colouring: Forest backbones in planar graphs, Discrete Applied Mathematics 169 (2014), 119–134.
D. B. West, Introduction to graph theory, 2nd ed., Prentice Hall, 2001.
Publicado
31/07/2022
Como Citar
ARAUJO, Julio; CEZAR, Alexandre; CASTRO, Rayane.
Galáxias como backbone em colorações backbone. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 89-92.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2022.223114.
