✦ LIBER ✦

On ordered sets without 2-colourings

✍ Scribed by Zbigniew Lonc

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 829 KB
Volume: 201
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(98)00318-5

No coin nor oath required. For personal study only.

✦ Synopsis

We say that an ordered set has a k-coloring if its elements can be colored with k colors such that no maximal nontrivial antichain is monochromatic. It was shown by Duffus, Kierstead and Trotter that each ordered set has a 3-coloring. Very few examples of ordered sets not admitting 2-colorings have been found so far. The smallest of them has 17 elements. We consider a certain subclass of the class of ordered of width 3 and prove a necessary condition satisfied by ordered sets in this subclass that are not 2-colorable. The condition allows us to find several new examples of ordered sets without a 2-coloring. Moreover we show that every ordered set without a 2-coloring in the considered subclass contains the above mentioned smallest known 17-element ordered set without a 2-coloring.

📜 SIMILAR VOLUMES

On a problem concerning ordered colourin

On a problem concerning ordered colourings

✍ Louis Caccetta; Rui Zhong Jia 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 192 KB

Let G be a connected graph with v(G)>~2 vertices and independence number ~(G). G is critical if for any edge e of G: (i) ~(G -e) > ct(G), if e is not a cut edge of G, and , 2, ife is a cut edge and Gi, G2 are the two components of G-e.

Matroids on Partially Ordered Sets

✍ Marilena Barnabei; Giorgio Nicoletti; Luigi Pezzoli 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 346 KB

## L dimension may be chosen within each of the subspaces L in the set S that are ''in general position.'' For example, in the real projective space of dimension 3, consider a plane , a line r not belonging to , the point P [ r l , and two distinct points Q, R both different from P, lying on the l

On c-homogeneous ordered sets

✍ Gerhard Behrendt 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 272 KB

Additive Utilities on Densely Ordered Se

Additive Utilities on Densely Ordered Sets

✍ Yutaka Nakamura 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 151 KB

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

Utility functions on ordered convex sets

✍ P.C. Fishburn 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 609 KB