Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

The Saturation Number for the Length of Degree Monotone Paths

Yair Caro;  Josef Lauri;  Christina Zarb — 2015

Discussiones Mathematicae Graph Theory

A degree monotone path in a graph G is a path P such that the sequence of degrees of the vertices in the order in which they appear on P is monotonic. The length (number of vertices) of the longest degree monotone path in G is denoted by mp(G). This parameter, inspired by the well-known Erdős- Szekeres theorem, has been studied by the authors in two earlier papers. Here we consider a saturation problem for the parameter mp(G). We call G saturated if, for every edge e added to G, mp(G + e) > mp(G),...

Constrained Colouring and σ-Hypergraphs

Yair Caro;  Josef Lauri;  Christina Zarb — 2015

Discussiones Mathematicae Graph Theory

A constrained colouring or, more specifically, an (α, β)-colouring of a hypergraph H, is an assignment of colours to its vertices such that no edge of H contains less than α or more than β vertices with different colours. This notion, introduced by Bujtás and Tuza, generalises both classical hypergraph colourings and more general Voloshin colourings of hypergraphs. In fact, for r-uniform hypergraphs, classical colourings correspond to (2, r)-colourings while an important instance of Voloshin colourings...

Page 1

Download Results (CSV)