| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:On the b-chromatic number of some graph products
Authors:Jakovac, Marko (Author)
Peterin, Iztok (Author)
Files:URL http://dx.doi.org/10.1556/SScMath.49.2012.2.1194
Work type:Not categorized (r6)
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
ISSN on article:0081-6906
COBISS_ID:16321113 New window
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
AddThis uses cookies that require your consent. Edit consent...

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ó
COBISS.SI-ID:7797770 New window

Secondary language

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.


Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
There are no comments!

Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica