Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "hereditary property of graphs" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-21 z 21
    Tytuł:
    Reducible properties of graphs
    Autorzy:
    Mihók, P.
    Semanišin, G.
    Powiązania:
    https://bibliotekanauki.pl/articles/972021.pdf
    Data publikacji:
    1995
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    additivity
    reducibility
    Opis:
    Let L be the set of all hereditary and additive properties of graphs. For P₁, P₂ ∈ L, the reducible property R = P₁∘P₂ is defined as follows: G ∈ R if and only if there is a partition V(G) = V₁∪ V₂ of the vertex set of G such that $⟨V₁⟩_G ∈ P₁$ and $⟨V₂⟩_G ∈ P₂$. The aim of this paper is to investigate the structure of the reducible properties of graphs with emphasis on the uniqueness of the decomposition of a reducible property into irreducible ones.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1995, 15, 1; 11-18
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The order of uniquely partitionable graphs
    Autorzy:
    Broere, Izak
    Frick, Marietjie
    Mihók, Peter
    Powiązania:
    https://bibliotekanauki.pl/articles/972025.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    uniquely partitionable graphs
    Opis:
    Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition {V₁,...,Vₙ} of V(G) such that, for each i = 1,...,n, the subgraph of G induced by $V_i$ has property $_i$. If a graph G has a unique (₁,...,ₙ)-partition we say it is uniquely (₁,...,ₙ)-partitionable. We establish best lower bounds for the order of uniquely (₁,...,ₙ)-partitionable graphs, for various choices of ₁,...,ₙ.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 1; 115-125
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Maximal graphs with respect to hereditary properties
    Autorzy:
    Broere, Izak
    Frick, Marietjie
    Semanišin, Gabriel
    Powiązania:
    https://bibliotekanauki.pl/articles/972029.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    maximal graphs
    vertex partition
    Opis:
    A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by V_i has property $P_i$; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R = P₁∘P₂. If P is a hereditary property, then a graph G is called P- maximal if G has property P but G+e does not have property P for every e ∈ E([G̅]). We present some general results on maximal graphs and also investigate P-maximal graphs for various specific choices of P, including reducible hereditary properties.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 1; 51-66
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Graphs maximal with respect to hom-properties
    Autorzy:
    Kratochvíl, Jan
    Mihók, Peter
    Semanišin, Gabriel
    Powiązania:
    https://bibliotekanauki.pl/articles/971980.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hom-property of graphs
    hereditary property of graphs
    maximal graphs
    Opis:
    For a simple graph H, →H denotes the class of all graphs that admit homomorphisms to H (such classes of graphs are called hom-properties). We investigate hom-properties from the point of view of the lattice of hereditary properties. In particular, we are interested in characterization of maximal graphs belonging to →H. We also provide a description of graphs maximal with respect to reducible hom-properties and determine the maximum number of edges of graphs belonging to →H.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 1; 77-88
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the factorization of reducible properties of graphs into irreducible factors
    Autorzy:
    Mihók, P.
    Vasky, R.
    Powiązania:
    https://bibliotekanauki.pl/articles/972030.pdf
    Data publikacji:
    1995
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    additivity
    reducibility
    vertex partition
    Opis:
    A hereditary property R of graphs is said to be reducible if there exist hereditary properties P₁,P₂ such that G ∈ R if and only if the set of vertices of G can be partitioned into V(G) = V₁∪V₂ so that ⟨V₁⟩ ∈ P₁ and ⟨V₂⟩ ∈ P₂. The problem of the factorization of reducible properties into irreducible factors is investigated.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1995, 15, 2; 195-203
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Uniquely partitionable graphs
    Autorzy:
    Bucko, Jozef
    Frick, Marietjie
    Mihók, Peter
    Vasky, Roman
    Powiązania:
    https://bibliotekanauki.pl/articles/972032.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    additivity
    reducibility
    vertex partition
    Opis:
    Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph $G[V_i]$ induced by $V_i$ has property $_i$; i = 1,...,n. A graph G is said to be uniquely (₁, ...,ₙ)-partitionable if G has exactly one (₁,...,ₙ)-partition. A property is called hereditary if every subgraph of every graph with property also has property . If every graph that is a disjoint union of two graphs that have property also has property , then we say that is additive. A property is called degenerate if there exists a bipartite graph that does not have property . In this paper, we prove that if ₁,..., ₙ are degenerate, additive, hereditary properties of graphs, then there exists a uniquely (₁,...,ₙ)-partitionable graph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 1; 103-113
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    -bipartitions of minor hereditary properties
    Autorzy:
    Borowiecki, Piotr
    Ivančo, Jaroslav
    Powiązania:
    https://bibliotekanauki.pl/articles/971979.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    minor hereditary property of graphs
    generalized colouring
    bipartitions of graphs
    Opis:
    We prove that for any two minor hereditary properties ₁ and ₂, such that ₂ covers ₁, and for any graph G ∈ ₂ there is a ₁-bipartition of G. Some remarks on minimal reducible bounds are also included.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 1; 89-93
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On generalized list colourings of graphs
    Autorzy:
    Borowiecki, Mieczysław
    Broere, Izak
    Mihók, Peter
    Powiązania:
    https://bibliotekanauki.pl/articles/972024.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    list colouring
    vertex partition number
    Opis:
    Vizing [15] and Erdős et al. [8] independently introduce the idea of considering list-colouring and k-choosability. In the both papers the choosability version of Brooks' theorem [4] was proved but the choosability version of Gallai's theorem [9] was proved independently by Thomassen [14] and by Kostochka et al. [11]. In [3] some extensions of these two basic theorems to (,k)-choosability have been proved.
    In this paper we prove some extensions of the well-known bounds for the -chromatic number to the (,k)-choice number and then an extension of Brooks' theorem.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 1; 127-132
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Generalized list colourings of graphs
    Autorzy:
    Borowiecki, Mieczysław
    Drgas-Burchardt, Ewa
    Mihók, Peter
    Powiązania:
    https://bibliotekanauki.pl/articles/972045.pdf
    Data publikacji:
    1995
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    list colouring
    vertex partition number
    Opis:
    We prove: (1) that $ch_P(G) - χ_P(G)$ can be arbitrarily large, where $ch_P(G)$ and $χ_P(G)$ are P-choice and P-chromatic numbers, respectively, (2) the (P,L)-colouring version of Brooks' and Gallai's theorems.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1995, 15, 2; 185-193
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Generalized domination, independence and irredudance in graphs
    Autorzy:
    Borowiecki, Mieczysław
    Michalak, Danuta
    Sidorowicz, Elżbieta
    Powiązania:
    https://bibliotekanauki.pl/articles/971966.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    generalized domination
    independence and irredundance numbers
    Opis:
    The purpose of this paper is to present some basic properties of -dominating, -independent, and -irredundant sets in graphs which generalize well-known properties of dominating, independent and irredundant sets, respectively.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 1; 147-153
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A survey of hereditary properties of graphs
    Autorzy:
    Borowiecki, Mieczysław
    Broere, Izak
    Frick, Marietjie
    Mihók, Peter
    Semanišin, Gabriel
    Powiązania:
    https://bibliotekanauki.pl/articles/971986.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    vertex partition
    reducible property
    graph invariants
    complexity
    Opis:
    In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 1; 5-50
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Gallais innequality for critical graphs of reducible hereditary properties
    Autorzy:
    Mihók, Peter
    Skrekovski, Riste
    Powiązania:
    https://bibliotekanauki.pl/articles/743466.pdf
    Data publikacji:
    2001
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    additive induced-hereditary property of graphs
    reducible property of graphs
    critical graph
    Gallai's Theorem
    Opis:
    In this paper Gallai's inequality on the number of edges in critical graphs is generalized for reducible additive induced-hereditary properties of graphs in the following way. Let $₁,₂,...,ₖ$ (k ≥ 2) be additive induced-hereditary properties, $ = ₁ ∘ ₂ ∘ ... ∘ₖ$ and $δ = ∑_{i=1}^k δ(_i)$. Suppose that G is an -critical graph with n vertices and m edges. Then 2m ≥ δn + (δ-2)/(δ²+2δ-2)*n + (2δ)/(δ²+2δ-2) unless = ² or $G = K_{δ+1}$. The generalization of Gallai's inequality for -choice critical graphs is also presented.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2001, 21, 2; 167-177
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Note on partitions of planar graphs
    Autorzy:
    Broere, Izak
    Wilson, Bonita
    Bucko, Jozef
    Powiązania:
    https://bibliotekanauki.pl/articles/744336.pdf
    Data publikacji:
    2005
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    planar graph
    hereditary property of graphs
    forest and triangle-free graph
    Opis:
    Chartrand and Kronk in 1969 showed that there are planar graphs whose vertices cannot be partitioned into two parts inducing acyclic subgraphs. In this note we show that the same is true even in the case when one of the partition classes is required to be triangle-free only.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 211-215
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On generating sets of induced-hereditary properties
    Autorzy:
    Semanišin, Gabriel
    Powiązania:
    https://bibliotekanauki.pl/articles/743561.pdf
    Data publikacji:
    2002
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    induced-hereditary property of graphs
    additivity
    reducibility
    generating sets
    maximal graphs
    unique factorization
    Opis:
    A natural generalization of the fundamental graph vertex-colouring problem leads to the class of problems known as generalized or improper colourings. These problems can be very well described in the language of reducible (induced) hereditary properties of graphs. It turned out that a very useful tool for the unique determination of these properties are generating sets. In this paper we focus on the structure of specific generating sets which provide the base for the proof of The Unique Factorization Theorem for induced-hereditary properties of graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2002, 22, 1; 183-192
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The decomposability of additive hereditary properties of graphs
    Autorzy:
    Broere, Izak
    Dorfling, Michael
    Powiązania:
    https://bibliotekanauki.pl/articles/743814.pdf
    Data publikacji:
    2000
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    property of graphs
    additive
    hereditary
    decomposable property of graphs
    Opis:
    An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If ₁,...,ₙ are properties of graphs, then a (₁,...,ₙ)-decomposition of a graph G is a partition E₁,...,Eₙ of E(G) such that $G[E_i]$, the subgraph of G induced by $E_i$, is in $_i$, for i = 1,...,n. We define ₁ ⊕...⊕ ₙ as the property {G ∈ : G has a (₁,...,ₙ)-decomposition}. A property is said to be decomposable if there exist non-trivial hereditary properties ₁ and ₂ such that = ₁⊕ ₂. We study the decomposability of the well-known properties of graphs ₖ, ₖ, ₖ, ₖ, ₖ, ₖ and $ ^{p}$.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2000, 20, 2; 281-291
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On a characterization of graphs by average labellings
    Autorzy:
    Harminc, Matúš
    Powiązania:
    https://bibliotekanauki.pl/articles/971968.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    property of graphs
    additive
    hereditary
    linear forest
    Opis:
    The additive hereditary property of linear forests is characterized by the existence of average labellings.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 1; 133-136
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Remarks on the existence of uniquely partitionable planar graphs
    Autorzy:
    Borowiecki, Mieczysław
    Mihók, Peter
    Tuza, Zsolt
    Voigt, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/744146.pdf
    Data publikacji:
    1999
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    property of graphs
    additive
    hereditary
    vertex partition
    uniquely partitionable graphs
    Opis:
    We consider the problem of the existence of uniquely partitionable planar graphs. We survey some recent results and we prove the nonexistence of uniquely (₁,₁)-partitionable planar graphs with respect to the property ₁ "to be a forest".
    Źródło:
    Discussiones Mathematicae Graph Theory; 1999, 19, 2; 159-166
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Generalized chromatic numbers and additive hereditary properties of graphs
    Autorzy:
    Broere, Izak
    Dorfling, Samantha
    Jonck, Elizabeth
    Powiązania:
    https://bibliotekanauki.pl/articles/743358.pdf
    Data publikacji:
    2002
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    property of graphs
    additive
    hereditary
    generalized chromatic number
    Opis:
    An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let and be additive hereditary properties of graphs. The generalized chromatic number $χ_{}()$ is defined as follows: $χ_{}() = n$ iff ⊆ ⁿ but $ ⊊ ^{n-1}$. We investigate the generalized chromatic numbers of the well-known properties of graphs ₖ, ₖ, ₖ, ₖ and ₖ.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2002, 22, 2; 259-270
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Unique factorization theorem
    Autorzy:
    Mihók, Peter
    Powiązania:
    https://bibliotekanauki.pl/articles/743745.pdf
    Data publikacji:
    2000
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    induced-hereditary
    additive property of graphs
    reducible property of graphs
    unique factorization
    uniquely partitionable graphs
    generating sets
    Opis:
    A property of graphs is any class of graphs closed under isomorphism. A property of graphs is induced-hereditary and additive if it is closed under taking induced subgraphs and disjoint unions of graphs, respectively. Let ₁,₂, ...,ₙ be properties of graphs. A graph G is (₁,₂,...,ₙ)-partitionable (G has property ₁ º₂ º... ºₙ) if the vertex set V(G) of G can be partitioned into n sets V₁,V₂,..., Vₙ such that the subgraph $G[V_i]$ of G induced by V_i belongs to $_i$; i = 1,2,...,n. A property is said to be reducible if there exist properties ₁ and ₂ such that = ₁ º₂; otherwise the property is irreducible. We prove that every additive and induced-hereditary property is uniquely factorizable into irreducible factors. Moreover the unique factorization implies the existence of uniquely (₁,₂, ...,ₙ)-partitionable graphs for any irreducible properties ₁,₂, ...,ₙ.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2000, 20, 1; 143-154
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Generalized edge-chromatic numbers and additive hereditary properties of graphs
    Autorzy:
    Dorfling, Michael
    Dorfling, Samantha
    Powiązania:
    https://bibliotekanauki.pl/articles/743370.pdf
    Data publikacji:
    2002
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    property of graphs
    additive
    hereditary
    generalized edge-chromatic number
    Opis:
    An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let and be hereditary properties of graphs. The generalized edge-chromatic number $ρ'_{}()$ is defined as the least integer n such that ⊆ n. We investigate the generalized edge-chromatic numbers of the properties → H, ₖ, ₖ, *ₖ, ₖ and ₖ.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2002, 22, 2; 349-359
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    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ł
      Wyświetlanie 1-21 z 21

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies