ǂThe ǂdistinguishing chromatic number of Cartesian products of two complete graphs

Janja Jerebic (Author), Sandi Klavžar (Author)

Abstract

Označitev grafa ▫$G$▫ je razlikovalna, če jo ohranja le trivialni avtomorfizem grafa ▫$G$▫. Razlikovalno kromatično število grafa ▫$G$▫ je najmanjše naravno število, za katero obstaja razlikovalna označitev grafa, ki je hkrati tudi dobro barvanje. Za vse ▫$k$▫ in ▫$n$▫ je določeno razlikovalno kromatično število kartezičnih produktov ▫$K_k\Box K_n$▫. V večini primerov je enako kromatičnemu številu, kar med drugim odgovori na vprašanje Choia, Hartkeja and Kaula, ali obstajajo še kakšni drugi grafi, za katere velja enakost.

Keywords

teorija grafov;razlikovalno kromatično število;grafovski avtomorfizem;kartezični produkt grafov;ne zaključna dela;graph theory;distinguishing chromatic number;graph automorphism;Cartesian product of graphs;

Data

Language:	English
Year of publishing:	2010
Typology:	1.08 - Published Scientific Conference Contribution
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.17
COBISS:	15552601
ISSN:	0012-365X
Views:	47
Downloads:	27
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Razlikovalno kromatično število kartezičnega produkta dveh polnih grafov
Secondary abstract:	A labeling of a graph ▫$G$▫ is distinguishing if it is only preserved by the trivial automorphism of ▫$G$▫. The distinguishing chromatic number of ▫$G$▫ is the smallest integer ▫$k$▫ such that ▫$G$▫ has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product $K_k\Box K_n$ is determined for all ▫$k$▫ and ▫$n$▫. In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds.
Secondary keywords:	Teorija grafov;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	Str. 1715-1720
DOI:	10.1016/j.disc.2009.11.021
ID:	1475074