Marko Jakovac (Author), Sandi Klavžar (Author)

Abstract

b-Kromatično število grafa ▫$G$▫ je največje celo število, za katero obstaja dobro ▫$k$▫-barvanje, v katerem vsak barvni razred vsebuje vsaj eno vozlišče, ki je sosednje z vsemi drugimi barvnimi razredi. Dokazano je, da je b-kromatično število kubičnih grafov enako 4 razen za Petersenov graf, ▫$K_{3,3}$▫, prizmo nad ▫$K_3$▫, in še en sporadičen primer na 10 vozliščih.

Keywords

teorija grafov;kromatično število;b-kromatično število;kubični graf;Petersenov graf;graph theory;chromatic number;b-chromatic number;cubic graph;Petersen graph;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UL FMF - Faculty of Mathematics and Physics
UDC: 519.174
COBISS: 15522905 Link will open in a new window
ISSN: 0911-0119
Views: 29
Downloads: 4
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Slovenian
Secondary title: b-Kromatično število kubičnih grafov
Secondary abstract: The b-chromatic number of a graph ▫$G$▫ is the largest integer ▫$k$▫ such that ▫$G$▫ admits a proper ▫$k$▫-coloring in which every color class contains at least one vertex adjacent to some vertex in all the other color classes. It is proved that with four exceptions, the b-chromatic number of cubic graphs is 4. The exceptions are the Petersen graph, ▫$K_{3,3}$▫, the prism over ▫$K_3$▫, and one more sporadic example on 10 vertices.
Secondary keywords: teorija grafov;kromatično število;b-kromatično število;kubični graf;Petersenov graf;
URN: URN:SI:UM:
Type (COBISS): Not categorized
Pages: str. 107-118
Volume: ǂVol. ǂ26
Issue: ǂno. ǂ1
Chronology: 2010
ID: 1475026