Chromatic numbers of strong product of odd cycles

Povzetek

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

Ključne besede

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;

Podatki

Jezik:	Angleški jezik
Leto izida:	2002
Tipologija:	1.08 - Objavljeni znanstveni prispevek na konferenci
Organizacija:	UM FS - Fakulteta za strojništvo
UDK:	519.174
COBISS:	13825113
ISSN:	1571-0653
Št. ogledov:	52
Št. prenosov:	37
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Kromatično število krepkega produkta lihih ciklov
Sekundarne ključne besede:	matematika;teorija grafov;krepki produkt grafov;kromatično število;lih cikel;minimalna neodvisna dominantna množica;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 647-652
Zvezek:	ǂVol. ǂ11
Čas izdaje:	July 2002
ID:	1472586