On the b-chromatic number of some graph products

Marko Jakovac (Avtor), Iztok Peterin (Avtor)

Povzetek

Pravilno barvanje vozlišč grafa kjer vsak barvni razred vsebuje vozlišče, ki ima soseda v vseh preostalih barvnih razredih, imenujemo b-barvanje. Največje naravno število ▫$\varphi (G)$▫, za katero obstaja b-barvanje grafa ▫$G$▫, imenujemo b-kromatično število. Določimo nekatere spodnje in zgornje meje b-kromatičnega števila za krepki produkt ▫$G\,\boxtimes\, H$▫, leksikografski produkt ▫$G[H]$▫ in za direktni produkt ▫$G\,\times\, H$▫. Prav tako določimo nekatere točne vrednosti za produkte poti, ciklov, zvezd in polnih dvodelnih grafov. Pokažemo tudi, da lahko določimo b-kromatično število za ▫$P_n \,\boxtimes\, H$▫, ▫$C_n \,\boxtimes\, H$▫, ▫$P_n[H]$▫, ▫$C_n[H]$▫ in ▫$K_{m,n}[H]$▫ za poljuben graf ▫$H$▫, če sta le ▫$m$▫ in ▫$n$▫ dovolj veliki.

Ključne besede

teorija grafov;b-kromatično število;krepki produkt;leksikografski produkt;direktni produkt;graph theory;b-chromatic number;strong product;lexicographic product;direct product;

Podatki

Jezik:	Angleški jezik
Leto izida:	2012
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK:	519.174
COBISS:	16321113
ISSN:	0081-6906
Št. ogledov:	291
Št. prenosov:	23
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	O b-kromatičnem številu nekaterih grafovskih produktov
Sekundarni povzetek:	A b-coloring is a proper vertex coloring of a graph such that each color class contains a vertex that has a neighbor in all other color classes and the b-chromatic number is the largest integer ▫$\varphi (G)$▫ for which a graph has a b-coloring with ▫$\varphi (G)$▫ colors. We determine some upper and lower bounds for the b-chromatic number of the strong product ▫$G \,\boxtimes\, H$▫, the lexicographic product ▫$G[H]$▫ and the direct product ▫$G \,\times\, H$▫ and give some exact values for products of paths, cycles, stars, and complete bipartite graphs. We also show that the b-chromatic number of ▫$P_n \,\boxtimes\, H$▫, ▫$C_n \,\boxtimes\, H$▫, ▫$P_n[H]$▫, ▫$C_n[H]$▫, and ▫$K_{m,n}[H]$▫ can be determined for an arbitrary graph ▫$H$▫, when integers ▫$m$▫ and ▫$n$▫ are large enough.
Sekundarne ključne besede:	teorija grafov;b-kromatično število;krepki produkt;leksikografski produkt;direktni produkt;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 156-169
Letnik:	Vol. 49
Zvezek:	no. 2
Čas izdaje:	2012
ID:	1476606