Veröffentlichung

Titel:

The interval number of a planar graph is at most three

AutorInnen:

Guillaume Guégan
Kolja Knauer
Jonathan Rollin
Torsten Ueckerdt

Kategorie:

Artikel in Zeitschriften

erschienen in:

Journal of Combinatorial Theory, Series B, Vol. 146, pp. 61-67, 2021

Abstract:

The interval number of a graph G is the minimum k such that one can assign to each vertex of G a union of k intervals on the real line, such that G is the intersection graph of these sets, i.e., two vertices are adjacent in G if and only if the corresponding sets of intervals have non-empty intersection. In 1983 Scheinerman and West [The interval number of a planar graph: Three intervals suffice. J.~Comb.~Theory, Ser.~B, 35:224--239, 1983] proved that the interval number of any planar graph is at most 3.
In this paper we present a flaw in the original proof and give another, different, and shorter proof of this result.

Download:

arXiv

BibTeX-Eintrag:

@article{GKRU21, title = "The interval number of a planar graph is at most three", journal = "Journal of Combinatorial Theory, Series B", volume = "146", pages = "61 - 67", year = "2021", doi = "https://doi.org/10.1016/j.jctb.2020.07.006", author = "Guillaume Guégan and Kolja Knauer and Jonathan Rollin and Torsten Ueckerdt", }