All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 52 Next

Displaying 1021 – 1040 of 5365

Showing per page

Color-bounded hypergraphs, V: host graphs and subdivisions

Csilla Bujtás, Zsolt Tuza, Vitaly Voloshin (2011)

Discussiones Mathematicae Graph Theory

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set = E₁,...,Eₘ, together with integers s i and t i satisfying 1 ≤ s i ≤ t i ≤ | E i | for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge E i satisfies s i ≤ | φ ( E i ) | ≤ t i . The hypergraph ℋ is colorable if it admits at least one proper coloring. We consider hypergraphs ℋ over a “host graph”, that means a graph G on the same vertex set X as ℋ, such that each E i induces a connected subgraph in G. In the current...

Coloring digraphs by iterated antichains

Svatopluk Poljak (1991)

Commentationes Mathematicae Universitatis Carolinae

We show that the minimum chromatic number of a product of two n -chromatic graphs is either bounded by 9, or tends to infinity. The result is obtained by the study of coloring iterated adjoints of a digraph by iterated antichains of a poset.

Coloring rectangular blocks in 3-space

Colton Magnant, Daniel M. Martin (2011)

Discussiones Mathematicae Graph Theory

If rooms in an office building are allowed to be any rectangular solid, how many colors does it take to paint any configuration of rooms so that no two rooms sharing a wall or ceiling/floor get the same color? In this work, we provide a new construction which shows this number can be arbitrarily large.

Coloring Some Finite Sets in ℝn

József Balogh, Alexandr Kostochka, Andrei Raigorodskii (2013)

Discussiones Mathematicae Graph Theory

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...

Coloring triangles and rectangles

Jindřich Zapletal (2023)

Commentationes Mathematicae Universitatis Carolinae

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 ℝ 2 does not.

Coloring with no 2-colored P 4 's.

Albertson, Michael O., Chappell, Glenn G., Kierstead, H.A., Kündgen, André, Ramamurthi, Radhika (2004)

The Electronic Journal of Combinatorics [electronic only]

Colouring game and generalized colouring game on graphs with cut-vertices

Elżbieta Sidorowicz (2010)

Discussiones Mathematicae Graph Theory

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 𝓗 ₖ.

Colouring graphs with prescribed induced cycle lengths

Bert Randerath, Ingo Schiermeyer (2001)

Discussiones Mathematicae Graph Theory

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 I ( 4 , 5 ) , the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of I ( 4 , 5 ) are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have...

Colouring of cycles in the de Bruijn graphs

Ewa Łazuka, Jerzy Żurawiecki (2000)

Discussiones Mathematicae Graph Theory

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....

Colouring polytopic partitions in ℝ d

Michal Křížek (2002)

Mathematica Bohemica

We consider face-to-face partitions of bounded polytopes into convex polytopes in ℝ d for arbitrary d ≥ 1 and examine their colourability. In particular, we prove that the chromatic number of any simplicial partition does not exceed d + 1 . Partitions of polyhedra in ℝ 3 into pentahedra and hexahedra are 5 - and 6 -colourable, respectively. We show that the above numbers are attainable, i.e., in general, they cannot be reduced.

Currently displaying 1021 – 1040 of 5365