TY - JOUR
T1 - A sharp edge bound on the interval number of a graph
AU - Balogh, József
AU - Pluhár, András
PY - 1999/10
Y1 - 1999/10
N2 - The interval number of a graph G, denoted by i(G), is the least natural number t such that G is the intersection graph of sets, each of which is the union of at most t intervals. Here we settle a conjecture of Griggs and West about bounding i(G) in terms of e, that is, the number of edges in G. Namely, it is shown that i(G) ≤ ⌈√e/2⌉ + 1. It is also observed that the edge bound induces i(G) ≤ √3γ(G)/2 + O(1), where γ(G) is the genus of G.
AB - The interval number of a graph G, denoted by i(G), is the least natural number t such that G is the intersection graph of sets, each of which is the union of at most t intervals. Here we settle a conjecture of Griggs and West about bounding i(G) in terms of e, that is, the number of edges in G. Namely, it is shown that i(G) ≤ ⌈√e/2⌉ + 1. It is also observed that the edge bound induces i(G) ≤ √3γ(G)/2 + O(1), where γ(G) is the genus of G.
KW - Density
KW - Griggs-West conjecture
KW - Interval number
UR - http://www.scopus.com/inward/record.url?scp=0033469419&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0033469419&partnerID=8YFLogxK
U2 - 10.1002/(SICI)1097-0118(199910)32:2<153::AID-JGT5>3.0.CO;2-P
DO - 10.1002/(SICI)1097-0118(199910)32:2<153::AID-JGT5>3.0.CO;2-P
M3 - Article
AN - SCOPUS:0033469419
SN - 0364-9024
VL - 32
SP - 153
EP - 159
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 2
ER -