Displaying similar documents to “The chromaticity of a family of 2-connected 3-chromatic graphs with five triangles and cyclomatic number six”

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

Relating 2-Rainbow Domination To Roman Domination

José D. Alvarado, Simone Dantas, Dieter Rautenbach (2017)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G, let R(G) and yr2(G) denote the Roman domination number of G and the 2-rainbow domination number of G, respectively. It is known that yr2(G) ≤ R(G) ≤ 3/2yr2(G). Fujita and Furuya [Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 161 (2013) 806-812] present some kind of characterization of the graphs G for which R(G) − yr2(G) = k for some integer k. Unfortunately, their result does not lead to an algorithm that allows to recognize...

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.

Remarks on the existence of uniquely partitionable planar graphs

Mieczysław Borowiecki, Peter Mihók, Zsolt Tuza, M. Voigt (1999)

Discussiones Mathematicae Graph Theory

Similarity:

We consider the problem of the existence of uniquely partitionable planar graphs. We survey some recent results and we prove the nonexistence of uniquely (𝓓₁,𝓓₁)-partitionable planar graphs with respect to the property 𝓓₁ "to be a forest".

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