Coloração de identificação local em grafos split-comparabilidade - Oliveira, Robson; Cappelle, Márcia; Coelho, Hebert; Nascimento, Julliano (Anais do Encontro de Teoria da Computação (ETC); 2026: Anais do XI Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2026.23412, 2026)
Uma coloração de identificação local (lid-coloração) é uma coloração própria de vértices tal que vértices adjacentes com vizinhanças fechadas distintas devem ser distinguidos pelos conjuntos de cores presentes nessas vizinhanças. O número lid-cromático χ lid (G) de um grafo G é o menor número de cores necessário em uma lid-coloração. Neste trabalho investigamos o número lid-cromático de uma subclasse de grafos split-comparabilidade, caracterizada por uma estrutura de vizinhança mais restrita, obtendo expressões exatas para χ lid (G) em função da estrutura do grafo e analisando o efeito da remoção de vértices gêmeos.