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

VL - 32

SP - 153

EP - 159

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 2

ER -