Displaying similar documents to “Maximal hypergraphs with respect to the bounded cost hereditary property”

On the cost chromatic number of outerplanar, planar, and line graphs

John Mitchem, Patrick Morriss, Edward Schmeichel (1997)

Discussiones Mathematicae Graph Theory

Similarity:

We consider vertex colorings of graphs in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of the coloring is the sum of the costs incurred at each vertex. The cost chromatic number of a graph with respect to a cost set is the minimum number of colors necessary to produce a minimum cost coloring of the graph. We show that the cost chromatic number of maximal outerplanar and maximal planar graphs can be arbitrarily large and...

Structural results on maximal k-degenerate graphs

Allan Bickle (2012)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is k-degenerate if its vertices can be successively deleted so that when deleted, each has degree at most k. These graphs were introduced by Lick and White in 1970 and have been studied in several subsequent papers. We present sharp bounds on the diameter of maximal k-degenerate graphs and characterize the extremal graphs for the upper bound. We present a simple characterization of the degree sequences of these graphs and consider related results. Considering edge coloring, we...

On graphs with maximum size in their switching classes

Sergiy Kozerenko (2015)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

In his PhD thesis [Structural aspects of switching classes, Leiden Institute of Advanced Computer Science, 2001] Hage posed the following problem: “characterize the maximum size graphs in switching classes”. These are called s-maximal graphs. In this paper, we study the properties of such graphs. In particular, we show that any graph with sufficiently large minimum degree is s-maximal, we prove that join of two s-maximal graphs is also an s-maximal graph, we give complete characterization...

Graphs maximal with respect to hom-properties

Jan Kratochvíl, Peter Mihók, Gabriel Semanišin (1997)

Discussiones Mathematicae Graph Theory

Similarity:

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.

Maximal graphs with respect to hereditary properties

Izak Broere, Marietjie Frick, Gabriel Semanišin (1997)

Discussiones Mathematicae Graph Theory

Similarity:

A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by Vi has property P i ; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R =...

Arithmetically maximal independent sets in infinite graphs

Stanisław Bylka (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Families of all sets of independent vertices in graphs are investigated. The problem how to characterize those infinite graphs which have arithmetically maximal independent sets is posed. A positive answer is given to the following classes of infinite graphs: bipartite graphs, line graphs and graphs having locally infinite clique-cover of vertices. Some counter examples are presented.

A note on maximal common subgraphs of the Dirac's family of graphs

Jozef Bucko, Peter Mihók, Jean-François Saclé, Mariusz Woźniak (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Let ⁿ be a given set of unlabeled simple graphs of order n. A maximal common subgraph of the graphs of the set ⁿ is a common subgraph F of order n of each member of ⁿ, that is not properly contained in any larger common subgraph of each member of ⁿ. By well-known Dirac’s Theorem, the Dirac’s family ⁿ of the graphs of order n and minimum degree δ ≥ [n/2] has a maximal common subgraph containing Cₙ. In this note we study the problem of determining all maximal common subgraphs of the Dirac’s...

On generating sets of induced-hereditary properties

Gabriel Semanišin (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A natural generalization of the fundamental graph vertex-colouring problem leads to the class of problems known as generalized or improper colourings. These problems can be very well described in the language of reducible (induced) hereditary properties of graphs. It turned out that a very useful tool for the unique determination of these properties are generating sets. In this paper we focus on the structure of specific generating sets which provide the base for the proof of The Unique...