TY - JOUR
T1 - The interval number of dense graphs
AU - Balogh, József
AU - Pluhár, Andres
N1 - Funding Information:
The ?rst author was partially supported by the OTKA grant F021271, the second by the Austrian-Hungarian Action Fund, while both by the OTKA grant F026049. ∗Corresponding author. E-mail addresses: [email protected] (J. Balogh), [email protected] (A. Pluha&r).
PY - 2002/9/28
Y1 - 2002/9/28
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 closed intervals. Most known bounds on i(G) are grossly excessive when G has more than half of the possible edges. A plausible remedy is to develop bounds on i(G) that are monotone decreasing in G. Here we bound i(G) in terms of e(Ḡ), the number of edges in the complement of G. We prove that i(G) ≤ [1/2√e(Ḡ)] + O(/z/logn).
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 closed intervals. Most known bounds on i(G) are grossly excessive when G has more than half of the possible edges. A plausible remedy is to develop bounds on i(G) that are monotone decreasing in G. Here we bound i(G) in terms of e(Ḡ), the number of edges in the complement of G. We prove that i(G) ≤ [1/2√e(Ḡ)] + O(/z/logn).
UR - http://www.scopus.com/inward/record.url?scp=31244437637&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=31244437637&partnerID=8YFLogxK
U2 - 10.1016/S0012-365X(01)00215-1
DO - 10.1016/S0012-365X(01)00215-1
M3 - Article
AN - SCOPUS:31244437637
SN - 0012-365X
VL - 256
SP - 423
EP - 429
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1-2
ER -