✦ LIBER ✦

On the stability number of the edge intersection of two graphs

✍ Scribed by Claudio Arbib; Alberto Caprara

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 38 KB
Volume: 83
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(01)00324-6

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be the graph obtained as the edge intersection of two graphs G 1 , G 2 on the same vertex set V . We show that if at

, where α() is the cardinality of the largest stable set. Moreover, for general G 1 and G 2 , we show that α(G) R(α(G 1 ) + 1, α(G 2 ) + 1) -1, where R(k, ) is the Ramsey number.

📜 SIMILAR VOLUMES

On the Number of Edges of Quadrilateral-

On the Number of Edges of Quadrilateral-Free Graphs

✍ Zoltán Füredi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 247 KB

If a graph has q 2 +q+1 vertices (q>13), e edges and no 4-cycles then e 1 2 q(q+1) 2 . Equality holds for graphs obtained from finite projective planes with polarities. This partly answers a question of Erdo s from the 1930's. 1996 Academic Press, Inc. ## 1. Results Let f (n) denote the maximum n

On the stability number of AH-free graph

On the stability number of AH-free graphs

✍ A. Hertz; D. de Werra 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 519 KB

## Abstract We describe a new class of graphs for which the stability number can be obtained in polynomial time. The algorithm is based on an iterative procedure that, at each step, builds from a graph __G__ a new graph __G^l^__ that has fewer nodes and has the property that α(__G^l^__) = α(__G__)

On hypergraphs without two edges interse

On hypergraphs without two edges intersecting in a given number of vertices

✍ P Frankl; Z Füredi 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 281 KB

On the Number of 3-Edge Colorings of Cub

On the Number of 3-Edge Colorings of Cubic Graphs

✍ Christian Szegedy 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 127 KB

In this paper we present a short algebraic proof for a generalization of a formula of R. Penrose, Some applications of negative dimensional tensors, in: Combinatorial Mathematics and its Applications Welsh (ed.), Academic Press, 1971, pp. 221-244 on the number of 3-edge colorings of a plane cubic gr

On the two-edge-colorings of perfect gra

On the two-edge-colorings of perfect graphs

✍ Chính T. Hoàng 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 409 KB 👁 1 views

## Abstract We investigate the conjecture that a graph is perfect if it admits a two‐edge‐coloring such that two edges receive different colors if they are the nonincident edges of a __P__~4~ (chordless path with four vertices). Partial results on this conjecture are given in this paper. © 1995 Joh

On the intersection of edges of a geomet

On the intersection of edges of a geometric graph by straight lines

✍ N. Alon; M.A. Perles 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 969 KB

A geometric graph ( = gg) is a pair G = (V, E), where V is a finite set of points ( = vertices) in general position in the plane, and E is a set of open straight line segments ( = edges) whose endpoints are in V. G is a convex gg ( = egg) if V is the set of vertices of a convex polygon. For n 3 1, 0