Scheinerman's conjecture

From Wikipedia, the free encyclopedia

In mathematics, Scheinerman's conjecture (1984) in graph theory states that every planar graph is the intersection graph of a set of line segments in the plane.

For instance, the graph G shown here

may be represented as the following intersection graph of segments. Here, vertices of G are represented by straight line segments and edges of G are represented by intersection points.

This conjecture has been settled in the particular case of 4-colored planar graphs with no separating cycle of length 4 whose vertices use all the four colors.

Scheinerman also conjectured that three directions could be sufficient for 3-colorable graphs, and D. West conjectured that similarly every (4-colorable) planar graph could be represented using 4 directions.

Conjecture: Every planar graph G is the intersection graph of a set of segments in the plane lying in χ(G) directions, where χ(G) is the chromatic number of G.

This conjecture has been settled for planar graphs having a 4-coloration of their vertices such that no separating cycle of length 4 gets all the 4 colors (this obviously includes all the 3-colorable planar graphs).

[edit] References

• N. de Castro, F. J. Cobos, J.C. Dana, and A. Márquez, Triangle-free planar graphs as segment intersection graphs, Journal of Graph Algorithms and Applications 6 (2002), no. 1, 7-26.
• H. de Fraysseix and P. Ossona de Mendez. Contact and intersection representations. In J. Pach, editor, Graph Drawing 2004, volume 3383 of Lecture Notes in Computer Science, pages 217-227. Springer Verlag, doi: 10.1007/b105810 2005.
• H. de Fraysseix, P. Ossona de Mendez, and J. Pach, Representation of planar graphs by segments, Intuitive Geometry 63 (1991), 109-117.
• E.R. Scheinerman, Intersection classes and multiple intersection parameters of graphs, Ph.D. thesis, Princeton University, 1984.
• D. West, Open problems, SIAM J. Discrete Math. Newslett. 2 (1991), no. 1, 10-12.