Sobre a skewness do produto cartesiano de estrelas e ciclos - Couto, Gabriel; Nigro, Mauro (Anais do Encontro de Teoria da Computação (ETC), 2025)
Um grafo G é planar quando pode ser representado num plano sem que suas arestas se cruzem. A skewness do grafo G, denotada por sk(G), é o menor número de arestas que precisam ser removidas de G para que o grafo resultante seja planar. O produto cartesiano dos grafos simples G = (V(G), E(G)) e H = (V(H), E(H)) é o grafo G□H cujo conjunto de vértices é V(G) × V(H) e cujo conjunto de arestas é o conjunto de todos os pares (u 1 , v 1 )(u 2 , v 2 ) de forma que ou u 1 u 2 ∈ E(G) e v 1 = v 2 , ou v 1 v 2 ∈ E(H) e u 1 = u 2 . Em 2024, Chia e Sim conjecturaram que sk(K 1,n □C m ) = (n − 2)⌊m−1/2 + 1⌋ para todo inteiro positivo n ≥ 2 e m ≥ 4. Neste artigo, provamos que para qualquer inteiro positivo n ≥ 2, sk(K 1,n □C 4 ) = 2(n− 2).