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 -