کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419254 | 683763 | 2016 | 7 صفحه PDF | دانلود رایگان |
The interval number i(G)i(G) of a graph GG is the least integer ii such that GG is the intersection graph of sets of at most ii intervals of the real line. The local track number l(G)l(G) is the least integer ll such that GG is the intersection graph of sets of at most ll 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)t(G) is the least integer tt such that E(G)E(G) is the union of tt 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.
Journal: Discrete Applied Mathematics - Volume 202, 31 March 2016, Pages 30–36