Vi studerar det konfliktfria kromatiska antalet χCF av grafer ur extrem och probabilistisk synvinkel. Vi löser en fråga om Pach och Tardos om det maximala konfliktfria kromatiskt tal som en n-vertexgraf kan ha. Vår konstruktion är slumpmässig. I samband med detta studerar vi utvecklingen av det konfliktfria kromatiska antalet av Erdős-Rényi random grafen G(n, p) och ger asymptotiken för p = (1/n). Vi visar också att för p ≥ 1/2 det konfliktfria kromatiska talet skiljer sig från dominansnumret med högst 3.
Glebov m.fl. REF utvidgar detta från en extrem och probabilistisk synpunkt genom att visa att nästan alla G(n, p)-grafer har konfliktfritt kromatiskt nummer O(log n) för p  på (1/n), och genom att ge en randomiserad konstruktion för grafer som har konfliktfritt kromatiskt nummer (log 2 n).
Conflict-free coloring of graphs
{'venue': None, 'journal': 'arXiv: Combinatorics', 'mag_field_of_study': ['Mathematics']}