✦ LIBER ✦

Chromatic Number and the 2-Rank of a Graph

✍ Scribed by C.D. Godsil; Gordon F. Royle

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 98 KB
Volume: 81
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.2003

No coin nor oath required. For personal study only.

✦ Synopsis

We show that if the adjacency matrix of a graph X has 2-rank 2r, then the chromatic number of X is at most 2 r +1, and that this bound is tight.

2001

📜 SIMILAR VOLUMES

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(∆

The star chromatic number of a graph

✍ H. L. Abbott; B. Zhou 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 469 KB 👁 2 views

## Abstract We study a generalization of the notion of the chromatic number of a graph in which the colors assigned to adjacent vertices are required to be, in a certain sense, far apart. © 1993 John Wiley & Sons, Inc.

The chromatic covering number of a graph

✍ Reza Naserasr; Claude Tardif 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB 👁 2 views

Following [1] , we investigate the problem of covering a graph G with induced subgraphs G 1 ; . . . ; G k of possibly smaller chromatic number, but such that for every vertex u of G, the sum of reciprocals of the chromatic numbers of the G i 's containing u is at least 1. The existence of such ''ch

Circular Chromatic Numbers and Fractiona

Circular Chromatic Numbers and Fractional Chromatic Numbers of Distance Graphs

✍ G.J. Chang; L. Huang; X. Zhu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 171 KB

This paper studies circular chromatic numbers and fractional chromatic numbers of distance graphs G(Z , D) for various distance sets D. In particular, we determine these numbers for those D sets of size two, for some special D sets of size three, for

The chromatic number of oriented graphs

✍ Sopena, Eric 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 2 views

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with

Real flow number and the cycle rank of a

Real flow number and the cycle rank of a graph

✍ Robert Lukot'ka; Martin Škoviera 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB

## Abstract This article establishes a relationship between the real (circular) flow number of a graph and its cycle rank. We show that a connected graph with real flow number __p__/__q__ + 1, where __p__ and __q__ are two relatively prime numbers must have cycle rank at least __p__ + __q__ − 1. A