Existem problemas para os quais não se conhece nenhum método computacionalmente eficiente de solução. Um desses problemas é o Problema da Coloração de Vértices e um algoritmo eficiente que o resolva vale um prêmio de um milhão de dólares, oferecido pelo Clay Mathematics Institute. Uma das formas de se atacar este problema é criando métodos eficientes para determinar o menor número de cores necessárias para colorir subconjuntos de grafos com propriedades específicas. Nesse trabalho, o Problema da Coloração de Vértices é estudado em um subconjunto de grafos chamado de grafos arco-circulares. Um grafo é arco-circular se cada vértice pode ser representado por um arco em uma   circunferência  de forma que existe  aresta  entre dois vértices se e somente se os arcos correspondentes tem interseção não-vazia. Sabe-se que o Problema da Coloração de Vértices é tão difícil nos grafos arco-circulares quanto é para um grafo qualquer. Por isso, mesmo a criação de um método computacionalmente eficiente que resolva o problema para os grafos arco-circulares é suficiente para se ganhar o prêmio do Clay Mathematics Institute.  Neste trabalho, determinamos o menor número de cores necessárias para colorir os vértices de alguns grafos arco-circulares. As provas são construtivas e resultam em algoritmos eficientes para resolver o Problema da Coloração de Vértices desses grafos.