Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring.

Bollobás, Béla

The search session has expired. Please query the service again.

Displaying similar documents to “Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring.”

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

𝓟-bipartitions of minor hereditary properties

Piotr Borowiecki, Jaroslav Ivančo (1997)

Discussiones Mathematicae Graph Theory

Similarity:

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.

On some variations of extremal graph problems

Gabriel Semanišin (1997)

Discussiones Mathematicae Graph Theory

Similarity:

A set P of graphs is termed hereditary property if and only if it contains all subgraphs of any graph G belonging to P. A graph is said to be maximal with respect to a hereditary property P (shortly P-maximal) whenever it belongs to P and none of its proper supergraphs of the same order has the property P. A graph is P-extremal if it has a the maximum number of edges among all P-maximal graphs of given order. The number of its edges is denoted by ex(n, P). If the number of edges...

On hereditary subdirectly irreducible graphs

Jiří Vinárek (1984)

Acta Universitatis Carolinae. Mathematica et Physica

Similarity:

Hereditarnia

Izak Broere, Peter Mihók (2013)

Discussiones Mathematicae Graph Theory

Similarity:

New results on generalized graph coloring.

Alekseev, Vladimir E., Farrugia, Alastair, Lozin, Vadim V. (2004)

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

Similarity:

Note on enumeration of labeled split graphs

Vladislav Bína, Jiří Přibil (2015)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

The paper brings explicit formula for enumeration of vertex-labeled split graphs with given number of vertices. The authors derive this formula combinatorially using an auxiliary assertion concerning number of split graphs with given clique number. In conclusion authors discuss enumeration of vertex-labeled bipartite graphs, i.e., a graphical class defined in a similar manner to the class of split graphs.

Dominating bipartite subgraphs in graphs

Gábor Bacsó, Danuta Michalak, Zsolt Tuza (2005)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.

Graphs Which Are Switching Equivalent To Their Complementary Line Graphs I

Slobodan K. Simić (1980)

Publications de l'Institut Mathématique

Similarity:

Universality for and in Induced-Hereditary Graph Properties

Izak Broere, Johannes Heidema (2013)

Discussiones Mathematicae Graph Theory

Similarity:

The well-known Rado graph R is universal in the set of all countable graphs I, since every countable graph is an induced subgraph of R. We study universality in I and, using R, show the existence of 2 א0 pairwise non-isomorphic graphs which are universal in I and denumerably many other universal graphs in I with prescribed attributes. Then we contrast universality for and universality in induced-hereditary properties of graphs and show that the overwhelming majority of induced-hereditary...