Número da sorte e grafos exoplanares livres de triângulos
Resumo
Uma coloração aditiva de um grafo G = (V,E) é uma função c : V → {1, 2, . . . , k} tal que, para toda aresta uv ∈ E, temos que Sc(u) ≠ Sc(v), onde Sc(u) = ∑v∈NG(u) c(v). O número da sorte de um grafo G, denotado por η(G), é definido como o menor valor de k tal que c seja uma coloração aditiva. Neste trabalho, provamos que se G é um grafo exoplanar livre de triângulos, então η(G) ≤ 6. Ademais, determinamos o número da sorte para os Snarks de Loupekine.
Referências
Michael O. Albertson e Emily H. Moore. Extending graph colorings using no extra colors. Discrete Math., 234(1-3):125–132, 2001.
Tomasz Bartnicki, Bartłomiej Bosek, Sebastian Czerwiński, Jarosław Grytczuk, Grzegorz Matecki, e Wiktor Żelazny. Additive coloring of planar graphs. Graphs Combin., 30(5):1087–1098, 2014.
Gary Chartrand, Futaba Okamoto, e Ping Zhang. The sigma chromatic number of a graph. Graphs Combin., 26(6):755–773, 2010.
Sebastian Czerwiński, Jarosław Grytczuk, e Wiktor Żelazny. Lucky labelings of graphs. Inform. Process. Lett., 109(18):1078–1081, 2009.
Ali Dehghan, Mohammad-Reza Sadeghi, e Arash Ahadi. Sigma partitioning: complexity and random graphs. Discrete Math. Theor. Comput. Sci., 20(2):Paper No. 19, 14, 2018.
Luis Gustavo da Soledade Gonzaga e Sheila Morais de Almeida. Sigma coloring on powers of paths and some families of Snarks. In The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019), volume 346 of Electron. Notes Theor. Comput. Sci., pages 485–496.
R Isaacs. Loupekhine’s Snarks: a bifamily of non-Tait-colorable graphs. J. Combin. Theory B, 1976.
Michał Karoński, Tomasz Łuczak, e Andrew Thomason. Edge weights and vertex colours. J. Combin. Theory Ser. B, 91(1):151–157, 2004.
Paul Adrian D. Luzon, Mari-Jo P. Ruiz, e Mark Anthony C. Tolentino. The sigma chromatic number of the circulant graphs Cn(1, 2), Cn(1, 3), and C2n(1, n). In Discrete and computational geometry and graphs, volume 9943 of Lecture Notes in Comput. Sci., pages 216–227.
Tomasz Bartnicki, Bartłomiej Bosek, Sebastian Czerwiński, Jarosław Grytczuk, Grzegorz Matecki, e Wiktor Żelazny. Additive coloring of planar graphs. Graphs Combin., 30(5):1087–1098, 2014.
Gary Chartrand, Futaba Okamoto, e Ping Zhang. The sigma chromatic number of a graph. Graphs Combin., 26(6):755–773, 2010.
Sebastian Czerwiński, Jarosław Grytczuk, e Wiktor Żelazny. Lucky labelings of graphs. Inform. Process. Lett., 109(18):1078–1081, 2009.
Ali Dehghan, Mohammad-Reza Sadeghi, e Arash Ahadi. Sigma partitioning: complexity and random graphs. Discrete Math. Theor. Comput. Sci., 20(2):Paper No. 19, 14, 2018.
Luis Gustavo da Soledade Gonzaga e Sheila Morais de Almeida. Sigma coloring on powers of paths and some families of Snarks. In The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019), volume 346 of Electron. Notes Theor. Comput. Sci., pages 485–496.
R Isaacs. Loupekhine’s Snarks: a bifamily of non-Tait-colorable graphs. J. Combin. Theory B, 1976.
Michał Karoński, Tomasz Łuczak, e Andrew Thomason. Edge weights and vertex colours. J. Combin. Theory Ser. B, 91(1):151–157, 2004.
Paul Adrian D. Luzon, Mari-Jo P. Ruiz, e Mark Anthony C. Tolentino. The sigma chromatic number of the circulant graphs Cn(1, 2), Cn(1, 3), and C2n(1, n). In Discrete and computational geometry and graphs, volume 9943 of Lecture Notes in Comput. Sci., pages 216–227.
Publicado
06/08/2023
Como Citar
SAMBINELLI, Maycon; SOUZA, Fabio dos Santos de.
Número da sorte e grafos exoplanares livres de triângulos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 64-68.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.229860.
