𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Colorings of diagrams of interval orders and α-sequences of sets

✍ Scribed by Stefan Felsner; William T. Trotter

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
383 KB
Volume
144
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We show that a proper coloring of the diagram of an interval order I may require 1 + I-log 2 height(l)] colors and that 2 + l-log 2 height(I)'] colors always suffice. For the proof of the upper bound we use the following fact: A sequence C 1 ...

.. C h of sets (of colors) with the property (ct)

C~C i\_lUC i for all l ¼N.

📜 SIMILAR VOLUMES

Theorems on intervals of ordered sets
Theorems on intervals of ordered sets
✍ Richard Rado 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 193 KB

VE I) be a family of such intervals. For NE I let V(N) be the chromatic number of the intersection graph 0; (A,,: Y E N), Theorem 1. Zf I is finite and A,, f1.4,,#0 for CL, YE I, tlren n,,, A# 6 Theorem 2. Let k IX a positiw integer and x(N) G k for INI = k + 1. Then x(Z) c k. XlleOrean 3. There is

On the complexity of interval orders and
On the complexity of interval orders and semiorders
✍ U. Faigle; Gy. Turán 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 607 KB

The recognition complexity of interval orders is shown to be Q(n log, n), and an optimal algorithm is given for the identification of semiorders. \* Supported by the joint research project "Algorithmic Aspects of Combinatorial Optimization" of the Hungarian Academy of Sciences (Magyar Tudomanyos Aka

Defining sets in vertex colorings of gra
Defining sets in vertex colorings of graphs and latin rectangles
✍ E.S. Mahmoodian; Reza Naserasr; Manouchehr Zaker 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 410 KB

In a given graph G, a set of vertices S with an assignment of colors is said to be a defining set of the vertex coloring of G, if there exists a unique extension of the colors of S to a z(G)coloring of the vertices of G. The concept of a defining set has been studied, to some extent, for block desig

Combination of interval-valued fuzzy set
Combination of interval-valued fuzzy set and soft set
✍ Xibei Yang; Tsau Young Lin; Jingyu Yang; Yan Li; Dongjun Yu 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 513 KB

The soft set theory, proposed by Molodtsov, can be used as a general mathematical tool for dealing with uncertainty. By combining the interval-valued fuzzy set and soft set models, the purpose of this paper is to introduce the concept of the interval-valued fuzzy soft set. The complement, ''AND'' an

The orders of graphs with prescribed deg
The orders of graphs with prescribed degree sets
✍ Timothy A. Sipka 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 321 KB 👁 1 views

## Abstract The degree set 𝒟^G^ of a graph __G__ is the set of degrees of the vertices of __G.__ For a finite nonempty set __S__ of positive integers, all positive integers __p__ are determined for which there exists a graph __G__ of order __p__ such that 𝒟^G^ = __S__.