Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 26

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Unique factorization theorem

100%
Mihók P.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 1
143-154
EN
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 𝓟₁,𝓟₂, ...,𝓟ₙ.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Gallai's innequality for critical graphs of reducible hereditary properties

64%
Mihók P., Skrekovski R.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 2
167-177
EN
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.
3
Content available remote

Fractional Q-Edge-Coloring of Graphs

64%
Czap J., Mihók P.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 3
509-519
EN
An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let [...] be an additive hereditary property of graphs. A [...] -edge-coloring of a simple graph is an edge coloring in which the edges colored with the same color induce a subgraph of property [...] . In this paper we present some results on fractional [...] -edge-colorings. We determine the fractional [...] -edge chromatic number for matroidal properties of graphs.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Prime ideals in the lattice of additive induced-hereditary graph properties

64%
Berger A., Mihók P.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 1
117-127
EN
An additive induced-hereditary property of graphs is any class of finite simple graphs which is closed under isomorphisms, disjoint unions and induced subgraphs. The set of all additive induced-hereditary properties of graphs, partially ordered by set inclusion, forms a completely distributive lattice. We introduce the notion of the join-decomposability number of a property and then we prove that the prime ideals of the lattice of all additive induced-hereditary properties are divided into two groups, determined either by a set of excluded join-irreducible properties or determined by a set of excluded properties with infinite join-decomposability number. We provide non-trivial examples of each type.
5
Content available remote

Hereditarnia

64%
Broere I., Mihók P.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
7-7
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On infinite uniquely partitionable graphs and graph properties of finite character

64%
Bucko J., Mihók P.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
241-251
EN
A graph property is any nonempty isomorphism-closed class of simple (finite or infinite) graphs. A graph property 𝓟 is of finite character if a graph G has a property 𝓟 if and only if every finite induced subgraph of G has a property 𝓟. Let 𝓟₁,𝓟₂,...,𝓟ₙ be graph properties of finite character, a graph G is said to be (uniquely) (𝓟₁, 𝓟₂, ...,𝓟ₙ)-partitionable if there is an (exactly one) partition {V₁, V₂, ..., Vₙ} of V(G) such that $G[V_i] ∈ 𝓟_i$ for i = 1,2,...,n. Let us denote by ℜ = 𝓟₁ ∘ 𝓟₂ ∘ ... ∘ 𝓟ₙ the class of all (𝓟₁,𝓟₂,...,𝓟ₙ)-partitionable graphs. A property ℜ = 𝓟₁ ∘ 𝓟₂ ∘ ... ∘ 𝓟ₙ, n ≥ 2 is said to be reducible. We prove that any reducible additive graph property ℜ of finite character has a uniquely (𝓟₁, 𝓟₂, ...,𝓟ₙ)-partitionable countable generating graph. We also prove that for a reducible additive hereditary graph property ℜ of finite character there exists a weakly universal countable graph if and only if each property $𝓟_i$ has a weakly universal graph.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Unique factorization theorem for object-systems

64%
Mihók P., Semanišin G.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 3
559-575
EN
The concept of an object-system is a common generalization of simple graph, digraph and hypergraph. In the theory of generalised colourings of graphs, the Unique Factorization Theorem (UFT) for additive induced-hereditary properties of graphs provides an analogy of the well-known Fundamental Theorem of Arithmetics. The purpose of this paper is to present UFT for object-systems. This result generalises known UFT for additive induced-hereditary and hereditary properties of graphs and digraphs. Formal Concept Analysis is applied in the proof.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On uniquely partitionable relational structures and object systems

64%
Bucko J., Mihók P.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 2
281-289
EN
We introduce object systems as a common generalization of graphs, hypergraphs, digraphs and relational structures. Let C be a concrete category, a simple object system over C is an ordered pair S = (V,E), where E = {A₁,A₂,...,Aₘ} is a finite set of the objects of C, such that the ground-set $V(A_i)$ of each object $A_i ∈ E$ is a finite set with at least two elements and $V ⊇ ⋃_{i=1}^m V(A_i)$. To generalize the results on graph colourings to simple object systems we define, analogously as for graphs, that an additive induced-hereditary property of simple object systems over a category C is any class of systems closed under isomorphism, induced-subsystems and disjoint union of systems, respectively. We present a survey of recent results and conditions for object systems to be uniquely partitionable into subsystems of given properties.
9
Content available remote

Universality in Graph Properties with Degree Restrictions

52%
Broere I., Heidema J., Mihók P.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 3
477-492
EN
Rado constructed a (simple) denumerable graph R with the positive integers as vertex set with the following edges: For given m and n with m < n, m is adjacent to n if n has a 1 in the m’th position of its binary expansion. It is well known that R is a universal graph in the set [...] of all countable graphs (since every graph in [...] is isomorphic to an induced subgraph of R). A brief overview of known universality results for some induced-hereditary subsets of [...] is provided. We then construct a k-degenerate graph which is universal for the induced-hereditary property of finite k-degenerate graphs. In order to attempt the corresponding problem for the property of countable graphs with colouring number at most k + 1, the notion of a property with assignment is introduced and studied. Using this notion, we are able to construct a universal graph in this graph property and investigate its attributes.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Generalized list colourings of graphs

52%
Borowiecki M., Drgas-Burchardt E., Mihók P.
Discussiones Mathematicae Graph Theory
|
1995
|
tom 15
|
nr 2
185-193
EN
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.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Generalized ramsey theory and decomposable properties of graphs

52%
Burr S., Jacobson M., Mihók P., Semanišin G.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
199-217
EN
In this paper we translate Ramsey-type problems into the language of decomposable hereditary properties of graphs. We prove a distributive law for reducible and decomposable properties of graphs. Using it we establish some values of graph theoretical invariants of decomposable properties and show their correspondence to generalized Ramsey numbers.
12
Content available remote

Fractional (P,Q)-Total List Colorings of Graphs

52%
Kemnitz A., Mihók P., Voigt M.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
167-179
EN
Let r, s ∈ N, r ≥ s, and P and Q be two additive and hereditary graph properties. A (P,Q)-total (r, s)-coloring of a graph G = (V,E) is a coloring of the vertices and edges of G by s-element subsets of Zr such that for each color i, 0 ≤ i ≤ r − 1, the vertices colored by subsets containing i induce a subgraph of G with property P, the edges colored by subsets containing i induce a subgraph of G with property Q, and color sets of incident vertices and edges are disjoint. The fractional (P,Q)-total chromatic number χ′′ f,P,Q(G) of G is defined as the infimum of all ratios r/s such that G has a (P,Q)-total (r, s)-coloring. A (P,Q)-total independent set T = VT ∪ET ⊆ V ∪E is the union of a set VT of vertices and a set ET of edges of G such that for the graphs induced by the sets VT and ET it holds that G[VT ] ∈ P, G[ET ] ∈ Q, and G[VT ] and G[ET ] are disjoint. Let TP,Q be the set of all (P,Q)-total independent sets of G. Let L(x) be a set of admissible colors for every element x ∈ V ∪ E. The graph G is called (P,Q)-total (a, b)-list colorable if for each list assignment L with |L(x)| = a for all x ∈ V ∪E it is possible to choose a subset C(x) ⊆ L(x) with |C(x)| = b for all x ∈ V ∪ E such that the set Ti which is defined by Ti = {x ∈ V ∪ E : i ∈ C(x)} belongs to TP,Q for every color i. The (P,Q)- choice ratio chrP,Q(G) of G is defined as the infimum of all ratios a/b such that G is (P,Q)-total (a, b)-list colorable. We give a direct proof of χ′′ f,P,Q(G) = chrP,Q(G) for all simple graphs G and we present for some properties P and Q new bounds for the (P,Q)-total chromatic number and for the (P,Q)-choice ratio of a graph G.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Graphs maximal with respect to hom-properties

52%
Kratochvíl J., Mihók P., Semanišin G.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
77-88
EN
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.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties

52%
Broere I., Bucko J., Mihók P.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
31-37
EN
Let 𝓟₁,𝓟₂,...,𝓟ₙ be graph properties, a graph G is said to be uniquely (𝓟₁,𝓟₂, ...,𝓟ₙ)-partitionable if there is exactly one (unordered) partition {V₁,V₂,...,Vₙ} of V(G) such that $G[V_i] ∈ 𝓟_i$ for i = 1,2,...,n. We prove that for additive and induced-hereditary properties uniquely (𝓟₁,𝓟₂,...,𝓟ₙ)-partitionable graphs exist if and only if $𝓟_i$ and $𝓟_j$ are either coprime or equal irreducible properties of graphs for every i ≠ j, i,j ∈ {1,2,...,n}.
15
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Partition problems and kernels of graphs

52%
Broere I., Hajnal P., Mihók P.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 2
311-313
16
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On generalized list colourings of graphs

52%
Borowiecki M., Broere I., Mihók P.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
127-132
EN
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.
17
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The order of uniquely partitionable graphs

52%
Broere I., Frick M., Mihók P.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
115-125
EN
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 𝓟₁,...,𝓟ₙ.
18
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Factorizations of properties of graphs

52%
Broere I., Teboho Moagi S., Mihók P., Vasky R.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
167-174
EN
A property of graphs is any isomorphism closed class of simple graphs. For given properties of graphs 𝓟₁,𝓟₂,...,𝓟ₙ a vertex (𝓟₁, 𝓟₂, ...,𝓟ₙ)-partition of a graph G is a partition {V₁,V₂,...,Vₙ} of V(G) such that for each i = 1,2,...,n the induced subgraph $G[V_i]$ has property $𝓟_i$. The class of all graphs having a vertex (𝓟₁, 𝓟₂, ...,𝓟ₙ)-partition is denoted by 𝓟₁∘𝓟₂∘...∘𝓟ₙ. A property 𝓡 is said to be reducible with respect to a lattice of properties of graphs 𝕃 if there are n ≥ 2 properties 𝓟₁,𝓟₂,...,𝓟ₙ ∈ 𝕃 such that 𝓡 = 𝓟₁∘𝓟₂∘...∘𝓟ₙ; otherwise 𝓡 is irreducible in 𝕃. We study the structure of different lattices of properties of graphs and we prove that in these lattices every reducible property of graphs has a finite factorization into irreducible properties.
19
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Remarks on the existence of uniquely partitionable planar graphs

52%
Borowiecki M., Mihók P., Tuza Z., Voigt M.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
159-166
EN
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".
20
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Uniquely partitionable graphs

52%
Bucko J., Frick M., Mihók P., Vasky R.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
103-113
EN
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.
first rewind previous Strona / 2 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.