✦ LIBER ✦

Some classical combinatorial problems on circulant and claw-free graphs: the isomorphism and coloring problems on circulant graphs and the stable set problem on claw-free graphs

✍ Scribed by Ugo Pietropaoli

Publisher: Springer
Year: 2008
Tongue: English
Weight: 98 KB
Volume: 7
Category: Article
ISSN: 1619-4500
DOI: 10.1007/s10288-008-0091-7

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On non-rank facets of the stable set pol

On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs

✍ Thomas M. Liebling; Gianpaolo Oriolo; Bianca Spille; Gautier Stauffer 📂 Article 📅 2004 🏛 Springer 🌐 English ⚖ 297 KB

Some results on the reconstruction probl

Some results on the reconstruction problems. p-claw-free, chordal, and p4-reducible graphs

✍ Bhalchandra D. Thatte 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 507 KB

## Abstract A claw is an induced subgraph isomorphic to K~1,3.~ The claw‐point is the point of degree 3 in a claw. A graph is called p‐claw‐free when no p‐cycle has a claw‐point on it. It is proved that for p ≥ 4, p‐claw‐free graphs containting at least one chordless p‐cycle are edge reconstructibl

On the max-cut problem for a planar, cub

On the max-cut problem for a planar, cubic, triangle-free graph, and the Chinese postman problem for a planar triangulation

✍ Carsten Thomassen 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

## Abstract Every 3‐connected planar, cubic, triangle‐free graph with __n__ vertices has a bipartite subgraph with at least 29__n__/24 − 7/6 edges. The constant 29/24 improves the previously best known constant 6/5 which was considered best possible because of the graph of the dodecahedron. Example