✦ LIBER ✦

Triangles in claw-free graphs

✍ Scribed by Hong Wang

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 642 KB
Volume: 187
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)00237-9

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to KI,3.

Let k be a positive integer. Our main result is as follows: If G is a claw-free graph of order at least 3k and d(x) + d(y)>~3k + 1 for every pair of non-adjacent vertices x and y of G, then G contains k vertex-disjoint triangles unless either k is odd and G is one exceptional graph of order 3k+ 1, or k is 1 and G is the union of vertex-disjoint cycles of length at least 4.

📜 SIMILAR VOLUMES

Almost claw-free graphs

✍ Zdeněk Ryjáček 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 374 KB

## Abstract We say that __G__ is almost claw‐free if the vertices that are centers of induced claws (__K__~1,3~) in __G__ are independent and their neighborhoods are 2‐dominated. Clearly, every claw‐free graph is almost claw‐free. It is shown that (i) every even connected almost claw‐free graph has

Quasi-claw-free graphs

✍ A. Ainouche 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 645 KB

A graph G is quasi claw-free if it satisfies the property: This property is satisfied if in particular u does not center a claw (induced K1.3). Many known results on claw-free graphs, dealing with matching and hamiltonicity are extended to the larger class of quasi-claw-free graphs.

Hamilton cycles in claw-free graphs

✍ Cun-Quan Zhang 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 299 KB 👁 2 views

Extending matchings in claw-free graphs

✍ Michael D. Plummer 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 506 KB

Let G be a graph with a perfect matching and let n be an integer, has a perfect matching for every pair of points u and v in V(G). It is proved that every 3-connected claw-free graph is bicritical and for n>2, every (2n+ l)-connected claw-free graph is n-extendable. Matching extension in planar an

Claw-free circular-perfect graphs

✍ Arnaud Pêcher; Xuding Zhu 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## Abstract The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that

Well-Covered Claw-Free Graphs

✍ David Tankus; Michael Tarsi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 336 KB