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 53 Next

Displaying 1041 – 1060 of 5365

Showing per page

Colouring vertices of plane graphs under restrictions given by faces

Július Czap, Stanislav Jendrol' (2009)

Discussiones Mathematicae Graph Theory

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

Combinatorics and quantifiers

Jaroslav Nešetřil (1996)

Commentationes Mathematicae Universitatis Carolinae

Let I m be the set of subsets of I of cardinality m . Let f be a coloring of I m and g a coloring of I m . We write f → g if every f -homogeneous H ⊆ I is also g -homogeneous. The least m such that f → g for some f : I m → k is called the k -width of g and denoted by w k ( g ) . In the first part of the paper we prove the existence of colorings with high k -width. In particular, we show that for each k > 0 and m > 0 there is a coloring g with w k ( g ) = m . In the second part of the paper we give applications of wide colorings in the theory of generalized quantifiers....

Combinatorics of Dyadic Intervals: Consistent Colourings

Anna Kamont, Paul F. X. Müller (2014)

Bulletin of the Polish Academy of Sciences. Mathematics

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 1041 – 1060 of 5365