An intersection graph of straight lines

Carsten Thomassen

doi:10.1016/S0012-365X(02)00591-5

An intersection graph of straight lines

Carsten Thomassen

Research output: Contribution to journal › Journal article › Research › peer-review

Abstract

G. Ehrlich, S. Even, and R.E. Tarjan conjectured that the graph obtained from a complete 3 partite graph K₄,₄,₄ by deleting the edges of four disjoint triangles is not the intersection graph of straight line segments in the plane. We show that it is.

Original language	English
Journal	Discrete Mathematics
Volume	259
Issue number	1-3
Pages (from-to)	359-360
ISSN	0012-365X
DOIs	https://doi.org/10.1016/S0012-365X(02)00591-5
Publication status	Published - 2002

Keywords

intersection graphs
straight lines

Access to Document

10.1016/S0012-365X(02)00591-5

OpenUrl availability

Check availability in DTU Findit

Cite this

@article{16c187a1f1854f76a3634a4b5457d43d,

title = "An intersection graph of straight lines",

abstract = "G. Ehrlich, S. Even, and R.E. Tarjan conjectured that the graph obtained from a complete 3 partite graph K4,4,4 by deleting the edges of four disjoint triangles is not the intersection graph of straight line segments in the plane. We show that it is.",

keywords = "intersection graphs, straight lines ",

author = "Carsten Thomassen",

year = "2002",

doi = "10.1016/S0012-365X(02)00591-5",

language = "English",

volume = "259",

pages = "359--360",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - An intersection graph of straight lines

AU - Thomassen, Carsten

PY - 2002

Y1 - 2002

N2 - G. Ehrlich, S. Even, and R.E. Tarjan conjectured that the graph obtained from a complete 3 partite graph K4,4,4 by deleting the edges of four disjoint triangles is not the intersection graph of straight line segments in the plane. We show that it is.

AB - G. Ehrlich, S. Even, and R.E. Tarjan conjectured that the graph obtained from a complete 3 partite graph K4,4,4 by deleting the edges of four disjoint triangles is not the intersection graph of straight line segments in the plane. We show that it is.

KW - intersection graphs

KW - straight lines

U2 - 10.1016/S0012-365X(02)00591-5

DO - 10.1016/S0012-365X(02)00591-5

M3 - Journal article

SN - 0012-365X

VL - 259

SP - 359

EP - 360

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

An intersection graph of straight lines

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this