The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Displaying 161 –
180 of
719
This note relates to bounds on the chromatic number χ(ℝn) of the Euclidean space, which is the minimum number of colors needed to color all the points in ℝn so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs Gn in ℝn was introduced showing that . For many years, this bound has been remaining the best known bound for the chromatic numbers of some lowdimensional spaces. Here we prove that and find an exact formula for the chromatic number in the case of...
It is consistent that ZF + DC holds, the hypergraph of rectangles on a given Euclidean space has countable chromatic number, while the hypergraph of equilateral triangles on does not.
For k ≥ 2 we define a class of graphs 𝓗 ₖ = {G: every block of G has at most k vertices}. The class 𝓗 ₖ contains among other graphs forests, Husimi trees, line graphs of forests, cactus graphs. We consider the colouring game and the generalized colouring game on graphs from 𝓗 ₖ.
In this paper we study the chromatic number of graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P₅-free or triangle-free, P₆-free and C₆-free graphs are 3-colourable. A canonical extension of these graph classes is , the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have...
We show that the problem of finding the family of all so called the locally reducible factors in the binary de Bruijn graph of order k is equivalent to the problem of finding all colourings of edges in the binary de Bruijn graph of order k-1, where each vertex belongs to exactly two cycles of different colours. In this paper we define and study such colouring for the greater class of the de Bruijn graphs in order to define a class of so called regular factors, which is not so difficult to construct....
We consider face-to-face partitions of bounded polytopes into convex polytopes in for arbitrary and examine their colourability. In particular, we prove that the chromatic number of any simplicial partition does not exceed . Partitions of polyhedra in into pentahedra and hexahedra are - and -colourable, respectively. We show that the above numbers are attainable, i.e., in general, they cannot be reduced.
We consider a vertex colouring of a connected plane graph G. A colour c is used k times by a face α of G if it appears k times along the facial walk of α. We prove that every connected plane graph with minimum face degree at least 3 has a vertex colouring with four colours such that every face uses some colour an odd number of times. We conjecture that such a colouring can be done using three colours. We prove that this conjecture is true for 2-connected cubic plane graphs. Next we consider other...
We study the problem of consistent and homogeneous colourings for increasing families of dyadic intervals. We determine when this problem can be solved and when it cannot.
Currently displaying 161 –
180 of
719