Sobre (2,1)-colorações em grafos exoplanares maximais

• A. L. Jonck Junior Unicamp http://orcid.org/0000-0002-5843-3832
• C. N. Campos Unicamp https://orcid.org/0000-0003-4237-4281

DOI: https://doi.org/10.5753/etc.2021.16380

Resumo

Uma $(m, d)$-coloração $\pi$ de um grafo $G$ é uma atribuição de $m$ cores aos vértices do grafo de maneira que, para todo vértice $u$ de $G$, no máximo $d$ vizinhos de $u$ possuem a cor $\pi(u)$. Neste trabalho, exibimos uma condição necessária para a existência de $(2,1)$-colorações em grafos exoplanares maximais com pelo menos quatro vértices.

Palavras-chave: Coloração de grafos, coloração defeituosa, grafos exoplanares

Referências

Andrews, J. A. and Jacobson, M. S. (1985). On a generalization of chromatic number. Congressus Numerantium, 47:33–48.

Angelini, P., Bekos, M. A., De Luca, F., Didimo, W., Kaufmann, M., Kobourov, S.,Montecchiani, F., Raftopoulou, C. N., Roselli, V., and Symvonis, A. (2017). Vertex-coloring with defects. Journal of Graph Algorithms and Applications, 21(3):313–340.

Choi, I. and Raspaud, A. (2015). Planar graphs with girth at least 5 are (3,5)-colorable. Discrete Mathematics, 338(4):661 – 667.

Cowen, L., Goddard, W., and Jesurum, C. E. (1997). Defective coloring revisited. Journalof Graph Theory, 24(3):205–219.

Cowen, L. J., Cowen, R. H., and Woodall, D. R. (1986). Defective colorings of graphsin surfaces: partitions into subgraphs of bounded valency. Journal of Graph Theory,10(2):187–195.

Dai, L., Wang, Y., and Xu, J. (2017). Every planar graph without cycles of length 4 or 9is (1,1,0)-colorable. Discrete Mathematics, 340(9):2108 – 2122.

Harary, F. (1985). Conditional colorability in graphs. In Graphs and applications, pages127–136. Wiley-Interscience Publication.

Huang, Z. (2020). Every planar graph without triangles adjacent to cycles of length 3 or 6 is (1,1,1)-colorable. Discrete Mathematics, 343(6):111846.

Karp, R. M. (1972). Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA.

Sittitrai, P. and Nakprasit, K. (2018). Defective 2-colorings of planar graphs without 4-cycles and 5-cycles. Discrete Mathematics, 341(8):2142 – 2150.

Xu, B. (2009). On(3,1)∗-coloring of plane graphs. SIAM Journal on Discrete Mathematics, 23(1):205–220.

Zhang, C., Wang, Y., and Chen, M. (2016). Planar graphs without adjacent cycles of length at most five are (1,1,0)-colorable. Discrete Mathematics, 339(12):3032 – 3042.