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", }
Jonathan Rollin | 10.05.2024