Displaying similar documents to “Recognizing the P 4 -structure of claw-free graphs and a larger graph class.”

Gallai and anti-Gallai graphs of a graph

S. Aparna Lakshmanan, S. B. Rao, A. Vijayakumar (2007)

Mathematica Bohemica

Similarity:

The paper deals with graph operators—the Gallai graphs and the anti-Gallai graphs. We prove the existence of a finite family of forbidden subgraphs for the Gallai graphs and the anti-Gallai graphs to be H -free for any finite graph H . The case of complement reducible graphs—cographs is discussed in detail. Some relations between the chromatic number, the radius and the diameter of a graph and its Gallai and anti-Gallai graphs are also obtained.

On the Non-(p−1)-Partite Kp-Free Graphs

Kinnari Amin, Jill Faudree, Ronald J. Gould, Elżbieta Sidorowicz (2013)

Discussiones Mathematicae Graph Theory

Similarity:

We say that a graph G is maximal Kp-free if G does not contain Kp but if we add any new edge e ∈ E(G) to G, then the graph G + e contains Kp. We study the minimum and maximum size of non-(p − 1)-partite maximal Kp-free graphs with n vertices. We also answer the interpolation question: for which values of n and m are there any n-vertex maximal Kp-free graphs of size m?