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 |
03/09/01 Colloquium
DR. CUN-QUAN ZHANG
DEPARTMENT OF MATHEMATICS
WEST VIRGINIA UNIVERSITY
DEPARTMENT OF MATHEMATICS
WEST VIRGINIA UNIVERSITY
Graph Colorings, Latin Squares, Cycle Covers, and Graph Embeddings
Abstract: An edge coloring of a graph is a mapping: such that no color appears at any vertex more than once. A graph is bipartite if the vertex set has a partition such that every edge joins vertices from different parts. Let G and H be two bipartite graphs. If H has the same degree sequence as that of G, then H is called a revision of G. A conjecture by Keedwell and Cameron was proved by us recently: Let G be a bipartite graph with the minimum degree at least 2. Then G must have a revision H that is simultaneously edge-colorable (that is, H has two proper edge-colorings such that (1) for any vertex, the set of colors appearing on edges at that vertex are the same in both colorings, and,(2) no edge receives the same color in both colorings.) The proof of the conjecture involves some methods and results related to integer flows and cycle covers, and is proved as a corollary of a stronger result that every bipartite graph with minimum degree at least 2 has a revision that admits a nowhere-zero 4-flow.