Número da sorte e grafos exoplanares livres de triângulos
Abstract
An additive coloring of a graph G = (V,E) is a function c : V → {1, 2, . . . , k} such that, for every edge uv ∈ E, we have Sc(u) ≠ Sc(v), where Sc(u) = ∑v∈NG(u) c(v). The lucky number of a graph G, denoted by η(G), is the smallest value of k such that exists an additive coloring c. In this work, we show that if G is a triangle-free outerplanar graph, then η(G) ≤ 6. Moreover, we determine the lucky number for Loupekine Snarks.
References
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.
Published
2023-08-06
How to Cite
SAMBINELLI, Maycon; SOUZA, Fabio dos Santos de.
Número da sorte e grafos exoplanares livres de triângulos. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
