On the chromatic number of set systems

An (r, l)‐system is an r‐uniform hypergraph in which every set of l vertices lies in at most one edge. Let m_k(r, l) be the minimum number of edges in an (r, l)‐system that is not k‐colorable. Using probabilistic techniques, we prove that where b_{r, l} is explicitly defined and a_{r, l} is sufficiently small. We also give a different argument proving (for even k) where a′_{r, l}=(r?l+1)/r(2^r?1re)^?l/(l?1). Our results complement earlier results of Erd?s and Lovász [10] who mainly focused on the case l=2, k fixed, and r large. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 87–98, 2001     

On the chromatic numbers of metric spaces with few forbidden distances

In this paper we will present some of our recent results concerning the chromatic numbers of different metric spaces.     

Borsuk's problem and the chromatic numbers of metric spaces

In this paper, we will give a short survey of various old and new results concerning two closely connected problems of combinatorial geometry - that of K. Borsuk and that of E. Nelson - P. Erdös - H. Hadwiger. We will also present here our very recent achievements on Ramsey numbers.     

关于偏序集相关联图的色数

对于每一个含有最小元素0的偏序集（P,≤）可以得到一个与其关联的图G（P）.本文主要通过代数的方法研究了所得关联图G（P）的性质,证明了如果G（P）的色数和团数是有限的,那么色数和团数都仅比P的极小素理想的个数大1.     

On fuzzy metric spaces

In this paper we introduce the concept of a fuzzy metric space. The distance between two points in a fuzzy metric space is a non-negative, upper semicontinuous, normal and convex fuzzy number. Properties of fuzzy metric spaces are studied and some fixed point theorems are proved.     

On a new generalization of metric spaces

In this paper, we introduce the \({\mathcal {F}}\)-metric space concept, which generalizes the metric space notion. We define a natural topology \(\tau _{{\mathcal {F}}}\) in such spaces and we study their topological properties. Moreover, we establish a new version of the Banach contraction principle in the setting of \({\mathcal {F}}\)-metric spaces. Several examples are presented to illustrate our study.     

On incompactness for chromatic number of graphs

We deal with incompactness. Assume the existence of non-reflecting stationary set of cofinality κ. We prove that one can define a graph G whose chromatic number is >κ, while the chromatic number of every subgraph G′?G, |G′|<|G| is ≦κ. The main case is κ=?₀.     

On the chromatic numbers of low-dimensional spaces

New lower bounds are found for the minimum number of colors needed to color all points of a Euclidean space in such a way that any two points at a distance of 1 have different colors.     

When removing an independent set is optimal for reducing the chromatic number

How large must the chromatic number of a graph be, in terms of the graph’s maximum degree, to ensure that the most efficient way to reduce the chromatic number by removing vertices is to remove an independent set? By a reduction to a powerful, known stability form of Brooks’ theorem, we answer this question precisely, determining the threshold to within two values (and indeed sometimes a unique value) for graphs of sufficiently large maximum degree.     

On the chromatic forcing number of a random graph

When we wish to compute lower bounds for the chromatic number χ(G) of a graph G, it is of interest to know something about the ‘chromatic forcing number’ f_χ(G), which is defined to be the least number of vertices in a subgraph H of G such that χ(H) = χ(G). We show here that for random graphs G_n,p with n vertices, f_χ(G_n,p) is almost surely at least ($\text{1}\text{2}$?ε)n, despite say the fact that the largest complete subgraph of G_n,p has only about log n vertices.     

On compactification of metric spaces

Iff:X →X* is a homeomorphism of a metric separable spaceX into a compact metric spaceX* such thatf(X)=X*, then the pair (f,X*) is called a metric compactification ofX. An absoluteG _δ-space (F _σ-space)X is said to be of the first kind, if there exists a metric compactification (f,X*) ofX such that , whereG _i are sets open inX* and dim[Fr(G _i)]<dimX. (Fr(G _i) being the boundary ofG _i and dimX — the dimension ofX). An absoluteG _δ-space (F _σ-space), which is not of the first kind, is said to be of the second kind. In the present paper spaces which are both absoluteG _δ andF _σ-spaces of the second kind are constructed for any positive finite dimension, a problem related to one of A. Lelek in [11] is solved, and a sufficient condition onX is given under which dim [X* −f(X)]≧k, for any metric compactification (f,X*) ofX, wherek≦dimX is a given number. This research has been sponsored by the U.S. Navy through the Office of Naval Research under contract No. 62558-3315.     

On the chromatic number of q-Kneser graphs

We show that the q-Kneser graph qK _2k:k (the graph on the k-subspaces of a 2k-space over GF(q), where two k-spaces are adjacent when they intersect trivially), has chromatic number q ^k ?+?q ^k?1 for k?=?3 and for k < q log q ? q. We obtain detailed results on maximal cocliques for k = 3.     

On the chromatic number of random graphs

In this paper we consider the classical Erdős–Rényi model of random graphs G_n,p. We show that for p=p(n)n^−3/4−δ, for any fixed δ>0, the chromatic number χ(G_n,p) is a.a.s. ℓ, ℓ+1, or ℓ+2, where ℓ is the maximum integer satisfying 2(ℓ−1)log(ℓ−1)p(n−1).     

On the chromatic number of rational five-space

Summary The chromatic number of rational five-space is the chromatic number of the infinite graph whose vertex set is the set of all those five-dimensional vectors with all the coordinates being rational numbers and with two vertices forming an edge iff the Euclidean distance is exactly one. In this paper it is shown that the chromatic number of rational five-space is at least six.     

On bounds for the incidentor chromatic number of a directed weighted multigraph

An incidentor coloring of a directed weighted multigraph is called admissible if: (a) the incidentors adjoining the same vertex are colored by different colors; (b) the difference between the colors of the final and initial incidentors of each arc is at least the weight of this arc. The minimum number of colors necessary for an admissible coloring of all incidentors of a multigraph G is bounded above and below. The upper and lower bounds differ by ┌Δ/2┐ where Δ is the degree of G.     

On an upper bound for the harmonious chromatic number of a graph

The upper bound for the harmonious chromatic number of a graph that has been given by Sin-Min Lee and John Mitchem is improved.