Displaying similar documents to “Problems from the world surrounding perfect graphs”

Distance perfectness of graphs

Andrzej Włoch (1999)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we propose a generalization of well known kinds of perfectness of graphs in terms of distances between vertices. We introduce generalizations of α-perfect, χ-perfect, strongly perfect graphs and we establish the relations between them. Moreover, we give sufficient conditions for graphs to be perfect in generalized sense. Other generalizations of perfectness are given in papers [3] and [7].

Some Variations of Perfect Graphs

Magda Dettlaff, Magdalena Lemańska, Gabriel Semanišin, Rita Zuazua (2016)

Discussiones Mathematicae Graph Theory

Similarity:

We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k ≥ 2. Moreover, we provide a complete characterisation of (ψ2 − γ1)- perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure...

On a perfect problem

Igor E. Zverovich (2006)

Discussiones Mathematicae Graph Theory

Similarity:

We solve Open Problem (xvi) from Perfect Problems of Chvátal [1] available at ftp://dimacs.rutgers.edu/pub/perfect/problems.tex: Is there a class C of perfect graphs such that (a) C does not include all perfect graphs and (b) every perfect graph contains a vertex whose neighbors induce a subgraph that belongs to C? A class P is called locally reducible if there exists a proper subclass C of P such that every graph in P contains a local subgraph...

Mycielskians and matchings

Tomislav Doslić (2005)

Discussiones Mathematicae Graph Theory

Similarity:

It is shown in this note that some matching-related properties of graphs, such as their factor-criticality, regularizability and the existence of perfect 2-matchings, are preserved when iterating Mycielski's construction.

Comparing imperfection ratio and imperfection index for graph classes

Arie M. C. A. Koster, Annegret K. Wagler (2008)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs G where the stable set polytope STAB ( G ) coincides with the fractional stable set polytope QSTAB ( G ) . For all imperfect graphs G it holds that STAB ( G ) QSTAB ( G ) . It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect. We discuss...

A note on strong and co-strong perfectness of the X-join of graphs

Alina Szelecka, Andrzej Włoch (1996)

Discussiones Mathematicae Graph Theory

Similarity:

Strongly perfect graphs were introduced by C. Berge and P. Duchet in [1]. In [4], [3] the following was studied: the problem of strong perfectness for the Cartesian product, the tensor product, the symmetrical difference of n, n ≥ 2, graphs and for the generalized Cartesian product of graphs. Co-strong perfectness was first studied by G. Ravindra andD. Basavayya [5]. In this paper we discuss strong perfectness and co-strong perfectness for the generalized composition (the lexicographic...

Forbidden Structures for Planar Perfect Consecutively Colourable Graphs

Marta Borowiecka-Olszewska, Ewa Drgas-Burchardt (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A consecutive colouring of a graph is a proper edge colouring with posi- tive integers in which the colours of edges incident with each vertex form an interval of integers. The idea of this colouring was introduced in 1987 by Asratian and Kamalian under the name of interval colouring. Sevast- janov showed that the corresponding decision problem is NP-complete even restricted to the class of bipartite graphs. We focus our attention on the class of consecutively colourable graphs whose...

On P4-tidy graphs.

Giakoumakis, V., Roussel, F., Thuillier, H. (1997)

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

Similarity:

On k-factor-critical graphs

Odile Favaron (1996)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is said to be k-factor-critical if the removal of any set of k vertices results in a graph with a perfect matching. We study some properties of k-factor-critical graphs and show that many results on q-extendable graphs can be improved using this concept.