Displaying similar documents to “On Large Chromatic Graphs Not Containing Prescribed Subgraphs”

The chromaticity of a family of 2-connected 3-chromatic graphs with five triangles and cyclomatic number six

Halina Bielak (1998)

Discussiones Mathematicae Graph Theory

Similarity:

In this note, all chromatic equivalence classes for 2-connected 3-chromatic graphs with five triangles and cyclomatic number six are described. New families of chromatically unique graphs of order n are presented for each n ≥ 8. This is a generalization of a result stated in [5]. Moreover, a proof for the conjecture posed in [5] is given.

On partitions of hereditary properties of graphs

Mieczysław Borowiecki, Anna Fiedorowicz (2006)

Discussiones Mathematicae Graph Theory

Similarity:

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

Some globally determined classes of graphs

Ivica Bošnjak, Rozália Madarász (2018)

Czechoslovak Mathematical Journal

Similarity:

For a class of graphs we say that it is globally determined if any two nonisomorphic graphs from that class have nonisomorphic globals. We will prove that the class of so called CCB graphs and the class of finite forests are globally determined.

Dominant-matching graphs

Igor' E. Zverovich, Olga I. Zverovich (2004)

Discussiones Mathematicae Graph Theory

Similarity:

We introduce a new hereditary class of graphs, the dominant-matching graphs, and we characterize it in terms of forbidden induced subgraphs.

γ-labelings of complete bipartite graphs

Grady D. Bullington, Linda L. Eroh, Steven J. Winters (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Explicit formulae for the γ-min and γ-max labeling values of complete bipartite graphs are given, along with γ-labelings which achieve these extremes. A recursive formula for the γ-min labeling value of any complete multipartite is also presented.