Como discutido em Diaconis e Mosteller (1989), o problema dos aniversários é um ponto importante de partida no estudo de coincidências. Uma definição de coincidência é adotada, seguida de uma breve apresentação dos seus principais aspectos: entre eles a subjetividade e a surpresa. Na literatura são encontradas as principais variações do problema dos aniversários, que analisadas, fornecem as bases para um estudo do aspecto probabilístico das coincidências. Neste trabalho os eventos são associados a variáveis aleatórias independentes e igualmente distribuídas, ou seja, os problema são estudados por técnicas de contagem. Desta forma o problema clássico dos aniversários pode ser associado à coloração dos vértices de um grafo completo, assim como o problema do aniversariante pode ser associado à coloração dos vértices de um grafo estrela. A partir destas observações, é proposta a formulação de problema dos aniversários sujeito a restrições de uma rede de relacionamentos, que equivale a um problema da coloração própria dos vértices de um grafo simples, cuja topologia modela as restrições do problema original. O objetivo do trabalho é aplicar o conhecimento desenvolvido sobre polinômios cromáticos no estudo das coincidências associadas a problemas dos aniversários sujeito a restrições, Um resumo sobre teoria dos grafos e os principais resultados referentes a polinômios cromáticos são apresentados com o objetivo de dar clareza e consistência entre definições adotadas, teoremas utilizados e sua aplicação nos casos de árvores de Cayley, grafos Bollobas-Chung e redes sociais simples. A análise das coincidências se concentra na determinação do polinômio cromático e suas representações em diferentes bases, entre elas as formas: de potência, fatorial e de árvore. A decisão se um grafo pode ou não ser colorido de maneira própria com k > 2 cores é um problema de decisão NP-completo, portanto um objetivo secundário é analisar as limitações dos algoritmos existentes e dos sistemas disponíveis para de calculo de polinômios cromáticos, que possuem coeficientes inteiros e podem alcançar centenas de dígitos. Os cálculos e as simulações foram realizadas no Sage Mathematics Software (Linux Version 8.8). A conclusão demonstra que o conhecimento e as técnicas de polinômios cromáticos contribuem com a solução da generalização proposta do problema dos aniversários, sendo analisadas as limitações atuais quanto à eficácia dos algoritmos disponíveis e a capacidade computacional demandada pela topologia do grafo associado ao problema original

As discussed in Diaconis e Mosteller (1989), the birthday problem is an important starting point in the study of coincidences. A definition of coincidence is adopted, followed by a brief presentation of its main aspects: subjectivity and surprise among them. In the literature, the main variations of the birthday problem are found, which analyzed, provide the basis for a study of the probabilistic aspect of coincidences. In this work the events are associated with independent and equally distributed random variables, that is, the problems are studied by counting techniques. Thus the classical birthday problem can be associated with the coloring of vertices of a complete graph, just as the birthmate problem can be associated with the coloring of the vertices of a star graph. From these observations, it is proposed a formulation of the birthday problem, subject to constraints of a relationships network, which is equivalent to a problem of proper coloring of the vertices of a simple graph, whose topology shapes the constraints of the original problem. The objective of this work is to apply the knowledge developed about chromatic polynomials in the study of coincidences associated with restricted birthday problems. A summary of graph theory and the main results concerning chromatic polynomials are presented with the purpose of providing clarity and consistency between adopted definitions, used theorems and their application in the case of Cayley trees, Bollobas-Chung graphs and simple social networks. The analysis of coincidences focuses on the determination of the chromatic polynomial and its representations in different bases, among them the power, factorial and tree bases. Whether or not a graph can be properly colored with k > 2 colors is an NP-complete decision problem, so a secondary objective is to analyze the limitations of existing algorithms and available systems for calculating chromatic polynomials, which have integer coefficients and can reach hundreds of digits. Calculations and simulations were performed in Sage Mathematics Software (Linux Version 8.8). The conclusion demonstrates that the knowledge and techniques of chromatic polynomials contribute to the solution of the proposed generalization of the birthdays problem, it is also analyzed the current limitations regarding the effectiveness of available algorithms and the computational capacity demanded by the graph topology associated with the original problem