The interval number of a planar graph is at most three
From MaRDI portal
Publication:2221918
DOI10.1016/j.jctb.2020.07.006zbMath1457.05025arXiv1805.02947OpenAlexW3048492929MaRDI QIDQ2221918
Kolja Knauer, Torsten Ueckerdt, Guillaume Guégan, Jonathan Rollin
Publication date: 3 February 2021
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.02947
Cites Work
- Recognizing graphs with fixed interval number is NP-complete
- The interval number of a planar graph: Three intervals suffice
- Three ways to cover a graph
- On star and caterpillar arboricity
- Interval representations of planar graphs
- Decomposing 4-connected planar triangulations into two trees and one path
- Caterpillar arboricity of planar graphs
- Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
- Planar Graphs as VPG-Graphs
- Visibility Number of Directed Graphs
- On double and multiple interval graphs
- A sharp edge bound on the interval number of a graph
- On the interval number of special graphs
- Every planar graph is the intersection graph of segments in the plane
- On interval representations of graphs