A note on the chromatic number of the square of the Cartesian product of two cycles

Zehui Shao (Avtor), Aleksander Vesel (Avtor)

Povzetek

The square ▫$G^2$▫ of a graph ▫$G$▫ is obtained from ▫$G$▫ by adding edges joining all pairs of nodes at distance 2 in ▫$G$▫. In this note we prove that ▫$\chi((C_m\Box C_n)^2) \le 6$ for $m, n \ge 40$▫. This confirms Conjecture 19 stated in [É. Sopena, J. Wu, Coloring the square of the Cartesian product of two cycles, Discrete Math. 310 (2010) 2327-2333].

Ključne besede

matematika;teorija grafov;kromatično število;kartezični produkt;označevanje grafov;kvadrat grafa;mathematics;graph theory;chromatic number;Cartesian product;graph labeling;square if a graph;

Podatki

Jezik:	Angleški jezik
Leto izida:	2013
Tipologija:	1.03 - Kratki znanstveni prispevek
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.17
COBISS:	19836168
ISSN:	0012-365X
Št. ogledov:	446
Št. prenosov:	23
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	O kromatičnem številu kvadrata kartezičnega produkta dveh ciklov
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 999-1001
Letnik:	Vol. 313
Zvezek:	iss. 9
Čas izdaje:	2013
ID:	1477048