Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: cyclic chromatic number

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

A note on cyclic chromatic number

100%

Zlámalová J.

Discussiones Mathematicae Graph Theory

2010

tom 30

nr 1

115-122

A cyclic colouring of a graph G embedded in a surface is a vertex colouring of G in which any two distinct vertices sharing a face receive distinct colours. The cyclic chromatic number $χ_c(G)$ of G is the smallest number of colours in a cyclic colouring of G. Plummer and Toft in 1987 conjectured that $χ_c(G) ≤ Δ* + 2$ for any 3-connected plane graph G with maximum face degree Δ*. It is known that the conjecture holds true for Δ* ≤ 4 and Δ* ≥ 18. The validity of the conjecture is proved in the paper for some special classes of planar graphs.

Unavoidable set of face types for planar maps

88%

Horňák M., Jendrol S.

Discussiones Mathematicae Graph Theory

1996

tom 16

nr 2

123-141

The type of a face f of a planar map is a sequence of degrees of vertices of f as they are encountered when traversing the boundary of f. A set 𝒯 of face types is found such that in any normal planar map there is a face with type from 𝒯. The set 𝒯 has four infinite series of types as, in a certain sense, the minimum possible number. An analogous result is applied to obtain new upper bounds for the cyclic chromatic number of 3-connected planar maps.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Horňák M.

1 Jendrol S.

1 Zlámalová J.

1 2010

1 1996

Wyniki wyszukiwania

A note on cyclic chromatic number

Unavoidable set of face types for planar maps