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

Povzetek

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.

Ključne besede

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;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UL FMF - Fakulteta za matematiko in fiziko
UDK: 519.174
COBISS: 15522905 Povezava se bo odprla v novem oknu
ISSN: 0911-0119
Št. ogledov: 29
Št. prenosov: 4
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarni naslov: b-Kromatično število kubičnih grafov
Sekundarni povzetek: 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.
Sekundarne ključne besede: teorija grafov;kromatično število;b-kromatično število;kubični graf;Petersenov graf;
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 107-118
Letnik: ǂVol. ǂ26
Zvezek: ǂno. ǂ1
Čas izdaje: 2010
ID: 1475026