Contact and intersection representations
De Fraysseix, Hubert ; Ossona De Mendez, Patrice
HAL, hal-00005645 / Harvested from HAL
Text on HAL
A necessary and sufficient condition is given for a connected bipartite graph to be the incidence graph of a family of segments and points. We deduce that any 4-connected 3-colorable plane graphs is the contact graphs of a family of segments and that any 4-colored planar graph without induced C4 using 4 colors is the intersection graph of a family of straight line segments.
Publié le : 2004-07-05
Classification:  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] 
@article{hal-00005645,
     author = {De Fraysseix, Hubert and Ossona De Mendez, Patrice},
     title = {Contact and intersection representations},
     journal = {HAL},
     volume = {2004},
     number = {0},
     year = {2004},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00005645}
}

De Fraysseix, Hubert; Ossona De Mendez, Patrice. Contact and intersection representations. HAL, Tome 2004 (2004) no. 0, . http://gdmltest.u-ga.fr/item/hal-00005645/