Wyniki wyszukiwania

1

Acyclic 6-Colouring of Graphs with Maximum Degree 5 and Small Maximum Average Degree

100%

Fiedorowicz A.

Discussiones Mathematicae Graph Theory

|

2013

|

tom 33

|

nr 1

91-99

EN

A k-colouring of a graph G is a mapping c from the set of vertices of G to the set {1, . . . , k} of colours such that adjacent vertices receive distinct colours. Such a k-colouring is called acyclic, if for every two distinct colours i and j, the subgraph induced by all the edges linking a vertex coloured with i and a vertex coloured with j is acyclic. In other words, every cycle in G has at least three distinct colours. Acyclic colourings were introduced by Gr¨unbaum in 1973, and since then have been widely studied. In particular, the problem of acyclic colourings of graphs with bounded maximum degree has been investigated. In 2011, Kostochka and Stocker showed that any graph with maximum degree 5 can be acyclically coloured with at most 7 colours. The question, whether this bound is achieved, remains open. In this note we prove that any graph with maximum degree 5 and maximum average degree at most 4 admits an acyclic 6-colouring. We also provide examples of graphs with these properties.

2

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

On partitions of hereditary properties of graphs

63%

Borowiecki M., Fiedorowicz A.

Discussiones Mathematicae Graph Theory

|

2006

|

tom 26

|

nr 3

377-387

EN

In this paper a concept 𝓠-Ramsey Class of graphs is introduced, where 𝓠 is a class of bipartite graphs. It is a generalization of well-known concept of Ramsey Class of graphs. Some 𝓠-Ramsey Classes of graphs are presented (Theorem 1 and 2). We proved that 𝓣₂, the class of all outerplanar graphs, is not 𝓓₁-Ramsey Class (Theorem 3). This results leads us to the concept of acyclic reducible bounds for a hereditary property 𝓟 . For 𝓣₂ we found two bounds (Theorem 4). An improvement, in some sense, of that in Theorem is given.

3

Maximal hypergraphs with respect to the bounded cost hereditary property

63%

Drgas-Burchardt E., Fiedorowicz A.

Discussiones Mathematicae Graph Theory

|

2005

|

tom 25

|

nr 1-2

67-77

EN

The hereditary property of hypergraphs generated by the cost colouring notion is considered in the paper. First, we characterize all maximal graphs with respect to this property. Second, we give the generating function for the sequence describing the number of such graphs with the numbered order. Finally, we construct a maximal hypergraph for each admissible number of vertices showing some density property. All results can be applied to the problem of information storage.

4

Acyclic reducible bounds for outerplanar graphs

51%

Borowiecki M., Fiedorowicz A., Hałuszczak M.

Discussiones Mathematicae Graph Theory

|

2009

|

tom 29

|

nr 2

219-239

EN

For a given graph G and a sequence 𝓟₁, 𝓟₂,..., 𝓟ₙ of additive hereditary classes of graphs we define an acyclic (𝓟₁, 𝓟₂,...,Pₙ)-colouring of G as a partition (V₁, V₂,...,Vₙ) of the set V(G) of vertices which satisfies the following two conditions: 1. $G[V_i] ∈ 𝓟_i$ for i = 1,...,n, 2. for every pair i,j of distinct colours the subgraph induced in G by the set of edges uv such that $u ∈ V_i$ and $v ∈ V_j$ is acyclic. A class R = 𝓟₁ ⊙ 𝓟₂ ⊙ ... ⊙ 𝓟ₙ is defined as the set of the graphs having an acyclic (𝓟₁, 𝓟₂,...,Pₙ)-colouring. If 𝓟 ⊆ R, then we say that R is an acyclic reducible bound for 𝓟. In this paper we present acyclic reducible bounds for the class of outerplanar graphs.

Ograniczanie wyników

4 Discussiones Mathematicae Graph Theory

4 Fiedorowicz A.

2 Borowiecki M.

1 Drgas-Burchardt E.

1 Hałuszczak M.

1 2013

1 2009

1 2006

1 2005

Acyclic 6-Colouring of Graphs with Maximum Degree 5 and Small Maximum Average Degree

On partitions of hereditary properties of graphs

Maximal hypergraphs with respect to the bounded cost hereditary property

Acyclic reducible bounds for outerplanar graphs