Wyniki wyszukiwania

1

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

On-line 𝓟-coloring of graphs

100%

Borowiecki P.

Discussiones Mathematicae Graph Theory

|

2006

|

tom 26

|

nr 3

389-401

EN

For a given induced hereditary property 𝓟, a 𝓟-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property 𝓟. We consider the effectiveness of on-line 𝓟-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function of any stingy on-line 𝓟-coloring algorithm. In the class of generalized trees, we characterize graphs critical for the greedy 𝓟-coloring. A class of graphs for which a greedy algorithm always generates optimal 𝓟-colorings for the property 𝓟 = K₃-free is given.

2

𝓟-bipartitions of minor hereditary properties

63%

Borowiecki P., Ivančo J.

Discussiones Mathematicae Graph Theory

|

1997

|

tom 17

|

nr 1

89-93

EN

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.

3

Partitions of some planar graphs into two linear forests

63%

Borowiecki P., Hałuszczak M.

Discussiones Mathematicae Graph Theory

|

1997

|

tom 17

|

nr 1

95-102

EN

A linear forest is a forest in which every component is a path. It is known that the set of vertices V(G) of any outerplanar graph G can be partitioned into two disjoint subsets V₁,V₂ such that induced subgraphs ⟨V₁⟩ and ⟨V₂⟩ are linear forests (we say G has an (LF, LF)-partition). In this paper, we present an extension of the above result to the class of planar graphs with a given number of internal vertices (i.e., vertices that do not belong to the external face at a certain fixed embedding of the graph G in the plane). We prove that there exists an (LF, LF)-partition for any plane graph G when certain conditions on the degree of the internal vertices and their neighbourhoods are satisfied.

4

Parity vertex colouring of graphs

51%

Borowiecki P., Budajová K., Jendrol' S., Krajci S.

Discussiones Mathematicae Graph Theory

|

2011

|

tom 31

|

nr 1

183-195

EN

A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T), then ⌈log₂(2+diam(T))⌉ ≤ χₚ(T) ≤ 1+rad(T). Both bounds are tight. The second thread of this paper is devoted to relationships between parity vertex colourings and vertex rankings, i.e. a proper vertex colourings with the property that each path between two vertices of the same colour q contains a vertex of colour greater than q. New results on graphs critical for vertex rankings are also presented.

Ograniczanie wyników

4 Discussiones Mathematicae Graph Theory

4 Borowiecki P.

1 Budajová K.

1 Hałuszczak M.

1 Ivančo J.

1 Jendrol' S.

1 Krajci S.

1 2011

1 2006

2 1997

On-line 𝓟-coloring of graphs

𝓟-bipartitions of minor hereditary properties

Partitions of some planar graphs into two linear forests

Parity vertex colouring of graphs