Results 261 to 270 of about 43,364 (297)
Some of the next articles are maybe not open access.
Journal of Graph Theory, 1999
A graph \(G\) is \text{perfect} if, for each induced subgraph \(G'\) of \(G\), the chromatic number of \(G'\) equals the maximum number of pairwise adjacent vertices in \(G'\). A graph \(G\) is \text{critically perfect} if \(G\) is perfect, has no isolated vertices, and, for each edge \(e\) of \(G\), \(G - e\) is not perfect.
exaly +3 more sources
A graph \(G\) is \text{perfect} if, for each induced subgraph \(G'\) of \(G\), the chromatic number of \(G'\) equals the maximum number of pairwise adjacent vertices in \(G'\). A graph \(G\) is \text{critically perfect} if \(G\) is perfect, has no isolated vertices, and, for each edge \(e\) of \(G\), \(G - e\) is not perfect.
exaly +3 more sources
A semi-induced subgraph characterization of upper domination perfect graphs [PDF]
Journal of Graph Theory, 1999 Let β(G) and Γ(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. The class of Γ-perfect graphs generalizes such well-known classes of
Igor E Zverovich
exaly +1 more source
A generalization of perfect graphs?i-perfect graphs
Journal of Graph Theory, 1996The \(i\)-chromatic number of \(G\), denoted \(\chi_i(G)\), is the least number \(k\) such that there is a \(k\)-colouring with no colour class inducing a \(K_{i+1}\) as a subgraph. The \(i\)-clique number, \(\omega_i(G)\), is defined to be \(\lceil \omega(G)/i\rceil\). An induced subgraph \(H\) of \(G\) is an \(i\)-transversal iff \(\omega(H)= i\) and
Leizhen Cai, Derek G. Corneil
openaire +2 more sources
Combinatorica, 1992
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
KORNER, JANOS +2 more
openaire +2 more sources
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
KORNER, JANOS +2 more
openaire +2 more sources
Cycle-perfect graphs are perfect
Journal of Graph Theory, 1996Given any graph \(G\), the cycle graph \(C(G)\) of \(G\) is defined by letting the vertices of \(C(G)\) be the induced cycles of \(G\); two induced cycles of \(G\) are adjacent in \(C(G)\) if they have in \(G\) at least one edge in common. \(G\) is called cycle-perfect if \(G\) and \(C(G)\) have no chordless cycles of odd length at least five.
openaire +2 more sources
ZOR Zeitschrift f�r Operations Research Methods and Models of Operations Research, 1990
Summary: The weak Berge hypothesis states that a graph is perfect if and only if its complement is perfect. Previous proofs of this hypothesis have used combinatorial or polyhedral methods. In this paper, the concept of norms related to graphs is used to provide an alternative proof for the weak Berge hypothesis.
Szczepan Perz, Stefan Rolewicz
openaire +2 more sources
Summary: The weak Berge hypothesis states that a graph is perfect if and only if its complement is perfect. Previous proofs of this hypothesis have used combinatorial or polyhedral methods. In this paper, the concept of norms related to graphs is used to provide an alternative proof for the weak Berge hypothesis.
Szczepan Perz, Stefan Rolewicz
openaire +2 more sources
Journal of Graph Theory, 1999
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +2 more sources
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +2 more sources
Information Processing Letters, 1994
The perfect graph approach to study the combinatorial structure of visibility graphs in polyominos can be traced back to a paper of Berge et al., who made a survey of results and a collection of problems related to polyominos. In more recent works, Rajeev, Motwani et al.
openaire +2 more sources
The perfect graph approach to study the combinatorial structure of visibility graphs in polyominos can be traced back to a paper of Berge et al., who made a survey of results and a collection of problems related to polyominos. In more recent works, Rajeev, Motwani et al.
openaire +2 more sources
Sci. Ann. Cuza Univ., 1993
The aim of this paper is to introduce a new class of perfect graphs, \(C\)-perfect graphs, which strictly contains perfectly orderable graphs and Meyniel graphs and is contained in the class of strongly perfect graphs.
Cornelius Croitoru, Costel Radu
openaire +1 more source
The aim of this paper is to introduce a new class of perfect graphs, \(C\)-perfect graphs, which strictly contains perfectly orderable graphs and Meyniel graphs and is contained in the class of strongly perfect graphs.
Cornelius Croitoru, Costel Radu
openaire +1 more source
Information Processing Letters, 1983
Abstract A perfect stable in a graph G is a stable S with the property that any vertex of G is either in S or adjacent with at least two vertices which are in S. This concept is an obvious generalization of the notion of perfect matching. In this note, the problem of deciding if a given graph has a perfect stable is considered.
Cornelius Croitoru, Emilian Suditu
openaire +1 more source
Abstract A perfect stable in a graph G is a stable S with the property that any vertex of G is either in S or adjacent with at least two vertices which are in S. This concept is an obvious generalization of the notion of perfect matching. In this note, the problem of deciding if a given graph has a perfect stable is considered.
Cornelius Croitoru, Emilian Suditu
openaire +1 more source