2015 | OriginalPaper | Buchkapitel
Probabilistic Arguments in Graph Coloring (Invited Talk)
verfasst von : C. R. Subramanian
Erschienen in: Algorithms and Discrete Applied Mathematics
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Probabilistic arguments has come to be a powerful way to obtain bounds on various chromatic numbers. It plays an important role not only in obtaining upper bounds but also in establishing the tightness of these upper bounds. It often calls for the application of various (often simple) ideas, tools and techniques (from probability theory) like moments, concentration inequalities, known estimates on tail probabilities and various other probability estimates. A number of examples illustrate how this approach can be a very useful tool in obtaining chromatic bounds. For many of these bounds, no other approach for obtaining them is known so far. In this talk, we illustrate this approach with some specific applications to graph coloring. On the other hand, several specific applications of this approach have also motivated and led to the development of powerful tools for handling discrete probability spaces. An important tool (for establishing the tightness results) is the notion of random graphs. We do not necessarily present the best results (obtained using this approach) since the main purpose is to provide an introduction to the power and simplicity of the approach. Many of the examples and the results are already known and published in the literature and have also been improved further.