for this workshop
The Albertson conjecture and related problems
American Institute of Mathematics, San Jose, California
Janos Pach, Andrew Suk, and Geza Toth
This workshop, sponsored by AIM and the NSF, is devoted to the Albertson conjecture and other problems related to crossing numbers. The crossing number of a graph is the minimum number of edge crossings in a drawing of the graph in the plane. Determining or estimating the crossing number of a graph is one of the oldest problems in graph theory, with over 700 papers written on the subject.
In 2007, Albertson made a tantalizing conjecture which would establish a relationship between the crossing number and the chromatic number of a graph. His conjecture states that if a graph requires at least r colors to properly color its vertices, then the crossing number of the graph is at least the crossing number of the complete graph on r vertices. We believe that the time is ripe to revisit this conjecture. We also intend to study some related problems which have proved particularly fruitful in recent years.
The main topics for the workshop are:
- Albertson's conjecture
- Quasi planar graphs
- Coloring intersection graphs
This event will be run as an AIM-style workshop. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.
The deadline to apply for support to participate in this workshop has passed.
For more information email firstname.lastname@example.org