𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On graphs with strongly independent color-classes

✍ Scribed by A. Gyárfás; T. Jensen; M. Stiebitz

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
148 KB
Volume
46
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We prove that for every k there is a k‐chromatic graph with a k‐coloring where the neighbors of each color‐class form an independent set. This answers a question raised by N. J. A. Harvey and U. S. R. Murty [4]. In fact we find the smallest graph G~k~ with the required property for every k. The graph G~k~ exhibits remarkable similarity to Kneser graphs. The proof that G~k~ is k‐chromatic relies on Lovász's theorem about the chromatic number of graphs with highly connected neighborhood complexes. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 1–14, 2004

📜 SIMILAR VOLUMES

Coloring plane graphs with independent c
Coloring plane graphs with independent crossings
✍ Daniel Král'; Ladislav Stacho 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB

## Abstract We show that every plane graph with maximum face size four in which all faces of size four are vertex‐disjoint is cyclically 5‐colorable. This answers a question of Albertson whether graphs drawn in the plane with all crossings independent are 5‐colorable. © 2009 Wiley Periodicals, Inc.

On Strongly Regular Graphs withμ =&
On Strongly Regular Graphs withμ =  1
✍ J. Deutsch; P.H. Fisher 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 75 KB

We consider strongly regular graphs in which each non-adjacent pair of vertices has exactly one common neighbour. These graphs give rise to partial linear spaces (one of which is a partial quadrangle) and a distance-regular graph of diameter three. The lower bound for the valency of the graph in ter

On graphs with subgraphs having large in
On graphs with subgraphs having large independence numbers
✍ Noga Alon; Benny Sudakov 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB

## Abstract Let __G__ be a graph on __n__ vertices in which every induced subgraph on ${s}={\log}^{3}\, {n}$ vertices has an independent set of size at least ${t}={\log}\, {n}$. What is the largest ${q}={q}{(n)}$ so that every such __G__ must contain an independent set of size at least __q__? This

On the Density of Subgraphs in a Graph w
On the Density of Subgraphs in a Graph with Bounded Independence Number
✍ Pavel Valtr 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 260 KB

Let \_(n, m, k) be the largest number \_ # [0, 1] such that any graph on n vertices with independence number at most m has a subgraph on k vertices with at lest \_ } ( k 2 ) edges. Up to a constant multiplicative factor, we determine \_(n, m, k) for all n, m, k. For log n m=k n, our result gives \_(