O número cromático de cliques de grafos aleatórios esparsos

O número cromático de cliques de um grafo é o menor número de cores em uma coloração de vértices de modo que nenhuma clique maximal seja monocromática. Neste artigo, determinamos a ordem de magnitude do número cromático de cliques do grafo G₍, ₏ para a maioria das probabilidades de arestas p na faixa n^-2/5 p 1. Isso resolve problemas e questões em aberto de Lichev, Mitsche e Warnke, bem como de Alon e Krievelevich. Uma dificuldade principal na prova decorre de vértices de alto grau, que impedem cliques maximais em seus vizinhos: lidamos com esses vértices por meio de um intrincado argumento de limite de união, que combina o método probabilístico com novos argumentos de contagem de grau para permitir a desigualdade de Janson. Dessa forma, determinamos a assintótica do número cromático de cliques de G₍, ₏ em algumas faixas e descobrimos um novo fenômeno surpreendente que contradiz previsões anteriores para probabilidades de arestas p próximas a n^-2/5.