Displaying similar documents to “Factors of claw-free graphs”

Minimal claw-free graphs

P. Dankelmann, Henda C. Swart, P. van den Berg, Wayne Goddard, M. D. Plummer (2008)

Czechoslovak Mathematical Journal

Similarity:

A graph G is a minimal claw-free graph (m.c.f. graph) if it contains no K 1 , 3 (claw) as an induced subgraph and if, for each edge e of G , G - e contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees of their vertices, and characterize graphs which have m.c.f. line graphs.

On a generalization of perfect b -matching

Ľubica Šándorová, Marián Trenkler (1991)

Mathematica Bohemica

Similarity:

The paper is concerned with the existence of non-negative or positive solutions to A f = β , where A is the vertex-edge incidence matrix of an undirected graph. The paper gives necessary and sufficient conditions for the existence of such a solution.

The perfection and recognition of bull-reducible Berge graphs

Hazel Everett, Celina M. H. de Figueiredo, Sulamita Klein, Bruce Reed (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices x , a , b , c , d and five edges x a , x b , a b , a d , b c . A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this result follows...