✦ LIBER ✦

k-Independence and thek-residue of a graph

✍ Scribed by Jelen, Frank

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 282 KB
Volume: 32
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199911)32:3<241::aid-jgt4>3.0.co;2-s

No coin nor oath required. For personal study only.

✦ Synopsis

Favaron, Mahéo, and Saclé proved that the residue of a simple graph G is a lower bound on its independence number α(G). For k ∈ N, a vertex set X in a graph is called k-independent, if the subgraph induced by X has maximum degree less than k. We prove that a generalization of the residue, the k-residue of a graph, yields a lower bound on the k-independence number. The new bound strengthens a bound of Caro and Tuza and improves all known bounds for some graphs.

📜 SIMILAR VOLUMES

k-Bounded classes of dominant-independen

k-Bounded classes of dominant-independent perfect graphs

✍ Zverovich, Igor E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 253 KB 👁 2 views

Let α(G), γ(G), and i(G) be the independence number, the domination number, and the independent domination number of a graph G, respectively. For any k ≥ 0, we define the following hereditary classes: αi where ISub(G) is the set of all induced subgraphs of a graph G. In this article, we present a f

Independence numbers of locally sparse g

Independence numbers of locally sparse graphs and a Ramsey type problem

✍ Noga Alon 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 409 KB

Let G = (V, E ) be a graph on n vertices with average degree t 2 1 in which for every vertex u E V the induced subgraph on the set of all neighbors of u is r-colorable. We show that the independence number of G is at least log t , for some absolute positive constant c. This strengthens a well-known

Clique-inverse graphs of K3-free and K4-

Clique-inverse graphs of K3-free and K4-free graphs

✍ Fábio Protti; Jayme L. Szwarcfiter 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 310 KB

A gap between the appearances of a k-cor

A gap between the appearances of a k-core and a (k + 1)-chromatic graph

✍ Michael Molloy 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB 👁 1 views

We observe that the values of p for which with high probability Gm,p is k-colorable and for which with high probability G,,p has no k-core are not equal for k 2 4.

Maximum independent sets of circular-arc

Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs

✍ Zheng, S. Q. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 421 KB 👁 2 views

We present a simple optimal algorithm for the problem of finding maximum independent sets of circular-arc graphs. Given an intersection model S of a circular-arc graph G , our algorithm computes a maximum independent set of G in O ( n ) space and O ( n ) or O(n log n ) time, depending on whether the

Rank and chromatic number of a graph

✍ Kotlov, Andrei? 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 2 views

It was proved (A. Kotlov and L. Lovász, The rank and size of graphs, J. Graph Theory 23 (1996), 185-189) that the number of vertices in a twin-free graph is O(( √ 2) r ) where r is the rank of the adjacency matrix. This bound was shown to be tight. We show that the chromatic number of a graph is o(∆