DisCoMath Seminar: Chromatic Vertex Folkman Numbers
Chromatic Vertex Folkman Numbers
Dr. Stanislaw Radziszowski
Professor
Department of Computer Science
Golisano College of Computing and Information Sciences, RIT
Register Here for Zoom Link
Abstract:
For graph G and integers a1≥⋯≥ar≥2, we write G→(a1,⋯,ar)v if and only if for every r-coloring of the vertex set V(G) there exists a monochromatic Kai in G for some color i∈{1,⋯,r}. The vertex Folkman number Fv(a1,⋯,ar;s) is defined as the smallest integer n for which there exists a Ks-free graph G of order n such that G→(a1,⋯,ar)v. It is well known that if G→(a1,⋯,ar)v then χ(G)≥m, where m=1+∑ri=1(ai−1). In this paper we study such Folkman graphs G with chromatic number χ(G)=m, which leads to a new concept of chromatic Folkman numbers. We prove constructively some existential results, among others that for all r,s≥2 there exist Ks+1-free graphs G such that G→(s,⋯r,s)v and G has the smallest possible chromatic number r(s−1)+1 with respect to this property. Among others we conjecture that for every s≥2 there exists a Ks+1-free graph G on Fv(s,s;s+1) vertices with χ(G)=2s−1 and G→(s,s)v.
Speaker Bio:
Stanislaw Radziszowski is a Professor in the Department of Computer Science since 1995. He earned Ph.D. from the Institute of Informatics at the University of Warsaw and since has been at RIT since 1984. Dr. Radziszowski’s main research interest is in combinatorial computing - solving classical problems in combinatorics, graph theory and design theory, usually with the help of massive computations. Bounds on Ramsey numbers are his favorite. His survey titled 'Small Ramsey Numbers', which is a regularly updated living article at the Electronic Journal of Combinatorics, became a standard reference in this area. He teaches mostly theory oriented courses, including very popular courses on cryptography, both at undergraduate and graduate levels. His recent work on applied cryptography led to joint projects with Computer Engineering Department.
Intended Audience:
Undergraduates, graduates, and experts. Those with interest in the topic.
Event Snapshot
When and Where
Who
This is an RIT Only Event
Interpreter Requested?
No