Temat: set chromatic number - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: A Tight Bound on the Set Chromatic Number
Autorzy:: Sereni, Jean-Sébastien
Yilma, Zelealem B.
Powiązania:: https://bibliotekanauki.pl/articles/30146528.pdf
Data publikacji:: 2013-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: chromatic number
set coloring
set chromatic number
neighbor
distinguishing coloring
Opis:: We provide a tight bound on the set chromatic number of a graph in terms of its chromatic number. Namely, for all graphs G, we show that χ_s(G) > ⌈log₂ χ(G)⌉ + 1, where χ_s(G) and χ(G) are the set chromatic number and the chromatic number of G, respectively. This answers in the affirmative a conjecture of Gera, Okamoto, Rasmussen and Zhang.
Źródło:: Discussiones Mathematicae Graph Theory; 2013, 33, 2; 461-465
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 2.

Tytuł:: The Quest for A Characterization of Hom-Properties of Finite Character
Autorzy:: Broere, Izak
Matsoha, Moroli D.V.
Heidema, Johannes
Powiązania:: https://bibliotekanauki.pl/articles/31340894.pdf
Data publikacji:: 2016-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: (countable) graph
homomorphism (of graphs)
property of graphs
hom-property
(finitely-)induced-hereditary property
finitely determined property
(weakly) finite character
axiomatizable property
compactness theorems
core
connectedness
chromatic number
clique number
independence number
dominating set
Opis:: A graph property is a set of (countable) graphs. A homomorphism from a graph \( G \) to a graph \( H \) is an edge-preserving map from the vertex set of \( G \) into the vertex set of \( H \); if such a map exists, we write \( G \rightarrow H \). Given any graph \( H \), the hom-property \( \rightarrow H \) is the set of \( H \)-colourable graphs, i.e., the set of all graphs \( G \) satisfying \( G \rightarrow H \). A graph property \( mathcal{P} \) is of finite character if, whenever we have that \( F \in \mathcal{P} \) for every finite induced subgraph \( F \) of a graph \( G \), then we have that \( G \in \mathcal{P} \) too. We explore some of the relationships of the property attribute of being of finite character to other property attributes such as being finitely-induced-hereditary, being finitely determined, and being axiomatizable. We study the hom-properties of finite character, and prove some necessary and some sufficient conditions on \( H \) for \( \rightarrow H \) to be of finite character. A notable (but known) sufficient condition is that \( H \) is a finite graph, and our new model-theoretic proof of this compactness result extends from hom-properties to all axiomatizable properties. In our quest to find an intrinsic characterization of those \( H \) for which \( \rightarrow H \) is of finite character, we find an example of an infinite connected graph with no finite core and chromatic number 3 but with hom-property not of finite character.
Źródło:: Discussiones Mathematicae Graph Theory; 2016, 36, 2; 479-500
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "set chromatic number" wg kryterium: Temat

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język