A teoria dos grafos começou com Euler em 1736, quando foi convidado a encontrar um caminho através das sete pontes da cidade de Köningsberg, passando uma única vez em cada ponte e retornando ao ponto inicial. Este problema, apesar de parecer simples, mostrou-se muito desafiador e originou a teoria dos grafos. Muitas situações reais podem ser convenientemente descritas por meio de um grafo — um diagrama que consiste em um conjunto de pontos, junto a um conjunto de linhas que unem certos pares desses pontos. O presente artigo ilustra um trabalho de iniciação científica, em andamento, cujo objetivo é o estudo dos grafos, aplicado à coloração de vértices, na resolução de um Sudoku 4x4. O estudo também almeja, futuramente, modelar um problema de alocação de horários. Para tal, fez-se uma apresentação sobre os conceitos básicos de grafos e de coloração de vértices, bem como a importância de suas aplicações; além da análise e do desenvolvimento de algoritmos de coloração, por meio do software MatLab.

Palavras-chave: grafo; coloração de vértices; MatLab; sudoku.