Coloração Harmoniosa - Araújo, Júlio C. S.; Martins, Ana Beatriz da S.; Santos, Marcio C. (Anais do Encontro de Teoria da Computação (ETC); 2022: Anais do VII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2022.223216, 2022)
Uma k-coloração c: V(G)->{1, 2, ..., k} é uma coloração linha-distinguível se cada par de arestas distintas tem conjuntos de cores distintos em suas extremidades. O número cromático linha-distinguível de G é λ (G)=min {k\in\mathbb{N}: G tem uma k-coloração linha-distinguível}. Se uma coloração linha-distinguível c é própria, então c é uma coloração harmoniosa. O número cromático harmonioso, denotado por h(G), é o menor k\in \mathbb{N} tal que G tem uma k-coloração harmoniosa. Neste trabalho, apresentamos uma condição necessária e suficiente para h(G) ser k, para um grafo arbitrário e k\in \mathbb{N}. Após isso, apresentamos formulações de programação inteira para computar h(G) e alguns testes preliminares em grafos aleatórios com densidades de arestas distintas.