Department
Home Page
About Us:
• Contact Info.
• Faculty
• Staff
• Students
Academic Program:
• Admission
• Undergraduate
• Graduate
• Certificates
Courses:
• Course Description
• Class Web Pages
• Class Syllabi
• Skills Tests
Research:
• Research Groups
• Colloquium
• Seminars
• News
Links:
| • Alumni Questionnaire |
| • Math Lab |
| • CAPA & Skills Tests |
| •Math Placement Test |
| • UCF Math Club |
| • Academic System Lab |
| • Careers |
| • American Mathematical Society |
| • Mathematical Association of America |
11/07/00 Colloquium
DR. ARUN MUKHERJEA
DEPARTMENT OF MATHEMATICS
UNIVERSITY OF SOUTH FLORIDA
DEPARTMENT OF MATHEMATICS
UNIVERSITY OF SOUTH FLORIDA
The Road-Coloring Problem
Abstract: Informally, this problem means the following: There are a number of buildings with a number of one-way roads connecting the buildings such that there are exactly two out-going roads from each building. (Graph-theoretically, there is a 2-out strongly connected digraph; the vertices can be looked upon as buildings and the directed arcs as one-way roads.) Under what conditions can one color the roads, so that the same set of instructions allows each person inside to get to the same building? This is a 23 year old unsolved problem which first appeared in a 1977 paper of Adler, Goodwyn and Weiss. In this talk, we will discuss this problem and a few known results.