Chromatic numbers of strong product of odd cycles

Abstract

The problem of determining the chromatic numbers of the strong product of cycles is considered. A construction is given proving ▫$\chi(G) = 2^p + 1$▫ for a product of ▫$p$▫ odd cycles of lengths at least ▫$2^p + 1$▫. Several consequences are discussed. In particular it is proved that the strong product of ▫$p$▫ factors has chromatic number at most ▫$2^p + 1$▫ provided that each factor admits the homomorphism to sufficiently long odd cycle ▫$C_{m_i}, \; m_i \ge 2^p + 1$▫.

Keywords

matematika;teorija grafov;krepki produkt grafov;kromatično število;lih cikel;minimalna neodvisna dominantna množica;mathematics;graph theory;strong product;chromatic number;odd cycle;minimal independent dominating set;

Data

Language:	English
Year of publishing:	2002
Typology:	1.08 - Published Scientific Conference Contribution
Organization:	UM FS - Faculty of Mechanical Engineering
UDC:	519.174
COBISS:	13825113
ISSN:	1571-0653
Views:	52
Downloads:	37
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Kromatično število krepkega produkta lihih ciklov
Secondary keywords:	matematika;teorija grafov;krepki produkt grafov;kromatično število;lih cikel;minimalna neodvisna dominantna množica;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 647-652
Issue:	ǂVol. ǂ11
Chronology:	July 2002
ID:	1472586