On the b-chromatic number of some graph products

Jakovac, Marko; Peterin, Iztok

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	On the b-chromatic number of some graph products
Authors:	ID Jakovac, Marko (Author) ID Peterin, Iztok (Author)
Files:	http://dx.doi.org/10.1556/SScMath.49.2012.2.1194
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FNM - Faculty of Natural Sciences and Mathematics
Abstract:	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.
Keywords:	teorija grafov, b-kromatično število, krepki produkt, leksikografski produkt, direktni produkt, graph theory, b-chromatic number, strong product, lexicographic product, direct product
Year of publishing:	2012
Number of pages:	str. 156-169
Numbering:	Vol. 49, no. 2
PID:	20.500.12556/DKUM-52004
UDC:	519.174
ISSN on article:	0081-6906
COBISS.SI-ID:	16321113
NUK URN:	URN:SI:UM:DK:LTQLPY02
Publication date in DKUM:	10.07.2015
Views:	1190
Downloads:	90
Metadata:
Categories:	Misc.
:	JAKOVAC, Marko and PETERIN, Iztok, 2012, On the b-chromatic number of some graph products. Studia scientiarum mathematicarum Hungarica [online]. 2012. Vol. 49, no. 2, p. 156–169. [Accessed 17 April 2025]. Retrieved from: http://dx.doi.org/10.1556/SScMath.49.2012.2.1194 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

No similar works found

Similar works from other repositories:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:	Studia scientiarum mathematicarum Hungarica
Shortened title:	Stud. sci. math. Hung.
Publisher:	Akadémiai Kiadó
ISSN:	0081-6906
COBISS.SI-ID:	7797770

Secondary language

Language:	English
Title:	O b-kromatičnem številu nekaterih grafovskih produktov
Abstract:	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.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back