Name
Abstract | ||
|---|---|---|
The interval number i ( G ) of a graph G is the least integer i such that G is the intersection graph of sets of at most i intervals of the real line. The local track number l ( G ) is the least integer l such that G is the intersection graph of sets of at most l intervals of the real line and such that two intervals of the same vertex belong to different components of the interval representation. The track number t ( G ) is the least integer t such that E ( G ) is the union of t interval graphs. We show that the local track number of a planar graph with girth at least 7 is at most 2. We also answer a question of West and Shmoys in 1984 by showing that the recognition of 2-degenerate planar graphs with maximum degree 5 and interval number at most 2 is NP-complete. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.dam.2015.08.022 | Discrete Applied Mathematics |
Keywords | Field | DocType |
planar graphs,np completeness | Discrete mathematics,Combinatorics,Indifference graph,Graph toughness,Line graph,Interval graph,Graph power,Pathwidth,1-planar graph,Intersection number (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
202 | C | 0166-218X |
Citations | PageRank | References |
1 | 0.37 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| aquiles braga de queiroz | 1 | 1 | 0.37 |
| Valentin Garnero | 2 | 12 | 3.31 |
| Pascal Ochem | 3 | 258 | 36.91 |