𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A sharp edge bound on the interval number of a graph

✍ Scribed by Balogh, J�zsef; Pluh�r, Andr�s

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
201 KB
Volume
32
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

A lower bound on the independence number
A lower bound on the independence number of arbitrary hypergraphs
✍ Thiele, Torsten 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB 👁 1 views

We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies α(H) ≥ v∈V f (d

Some new bounds for the maximum number o
Some new bounds for the maximum number of vertex colorings of a (v,e)-graph
✍ Byer, Owen D. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

Let f (v, e, λ) denote the maximum number of proper vertex colorings of a graph with v vertices and e edges in λ colors. In this paper we present some new upper bounds for f (v, e, λ). In particular, a new notion of pseudoproper colorings of a graph is given, which allows us to significantly improve

The edge chromatic number of a directed/
The edge chromatic number of a directed/mixed multigraph
✍ Mel'nikov, Leonid S.; Vizing, Vadim G. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB 👁 1 views

We consider colorings of the directed and undirected edges of a mixed multigraph G by an ordered set of colors. We color each undirected edge in one color and each directed edge in two colors, such that the color of the first half of a directed edge is smaller than the color of the second half. The

On some simple degree conditions that gu
On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs
✍ Vu, Van H. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB 👁 2 views

It is well known that almost every graph in the random space G(n, p) has chromatic number of order O(np/ log(np)), but it is not clear how we can recognize such graphs without eventually computing the chromatic numbers, which is NP-hard. The first goal of this article is to show that the above-menti