Currently displaying 1 – 20 of 20

Showing per page

Order by Relevance | Title | Year of publication

Chromatic polynomials of hypergraphs

Mieczysław BorowieckiEwa Łazuka — 2000

Discussiones Mathematicae Graph Theory

In this paper we present some hypergraphs which are chromatically characterized by their chromatic polynomials. It occurs that these hypergraphs are chromatically unique. Moreover we give some equalities for the chromatic polynomials of hypergraphs generalizing known results for graphs and hypergraphs of Read and Dohmen.

On partitions of hereditary properties of graphs

Mieczysław BorowieckiAnna Fiedorowicz — 2006

Discussiones Mathematicae Graph Theory

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,...

Weakly P-saturated graphs

Mieczysław BorowieckiElżbieta Sidorowicz — 2002

Discussiones Mathematicae Graph Theory

For a hereditary property let k ( G ) denote the number of forbidden subgraphs contained in G. A graph G is said to be weakly -saturated, if G has the property and there is a sequence of edges of G̅, say e , e , . . . , e l , such that the chain of graphs G = G G 0 + e G + e . . . G l - 1 + e l = G l = K n ( G i + 1 = G i + e i + 1 ) has the following property: k ( G i + 1 ) > k ( G i ) , 0 ≤ i ≤ l-1. In this paper we shall investigate some properties of weakly saturated graphs. We will find upper bound for the minimum number of edges of weakly ₖ-saturated graphs of order n. We shall determine the number wsat(n,) for some...

Hamiltonicity and Generalised Total Colourings of Planar Graphs

Mieczysław BorowieckiIzak Broere — 2016

Discussiones Mathematicae Graph Theory

The total generalised colourings considered in this paper are colourings of graphs such that the vertices and edges of the graph which receive the same colour induce subgraphs from two prescribed hereditary graph properties while incident elements receive different colours. The associated total chromatic number is the least number of colours with which this is possible. We study such colourings for sets of planar graphs and determine, in particular, upper bounds for these chromatic numbers for proper...

On generalized list colourings of graphs

Mieczysław BorowieckiIzak BroerePeter Mihók — 1997

Discussiones Mathematicae Graph Theory

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...

Acyclic reducible bounds for outerplanar graphs

Mieczysław BorowieckiAnna FiedorowiczMariusz Hałuszczak — 2009

Discussiones Mathematicae Graph Theory

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,...

A survey of hereditary properties of graphs

Mieczysław BorowieckiIzak BroereMarietjie FrickPeter MihókGabriel Semanišin — 1997

Discussiones Mathematicae Graph Theory

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.

Generalized total colorings of graphs

Mieczysław BorowieckiArnfried KemnitzMassimiliano MarangioPeter Mihók — 2011

Discussiones Mathematicae Graph Theory

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let P and Q be additive hereditary properties of graphs. A (P,Q)-total coloring of a simple graph G is a coloring of the vertices V(G) and edges E(G) of G such that for each color i the vertices colored by i induce a subgraph of property P, the edges colored by i induce a subgraph of property Q and incident vertices and edges obtain different colors. In this paper we present...

On extremal sizes of locally k -tree graphs

Mieczysław BorowieckiPiotr BorowieckiElżbieta SidorowiczZdzisław Skupień — 2010

Czechoslovak Mathematical Journal

A graph G is a if for any vertex v the subgraph induced by the neighbours of v is a k -tree, k 0 , where 0 -tree is an edgeless graph, 1 -tree is a tree. We characterize the minimum-size locally k -trees with n vertices. The minimum-size connected locally k -trees are simply ( k + 1 ) -trees. For k 1 , we construct locally k -trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an n -vertex locally k -tree graph is between Ω ( n ) and O ( n 2 ) , where both bounds are asymptotically...

Page 1 Next

Download Results (CSV)