✦ LIBER ✦

Chromatic factorizations of a graph

✍ Scribed by S. Louis Hakimi; Edward F. Schmeichel

Publisher: John Wiley and Sons
Year: 1988
Tongue: English
Weight: 243 KB
Volume: 12
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190120207

No coin nor oath required. For personal study only.

✦ Synopsis

Let n, 2 n2 L . . B n, 2 2 be integers. We say that G has an (n,, n2, , . , , n,)-chromatic factorization if G can be edge-factored as G, @ G2 @ + . . @ G, with x ( G , ) = n,, for i = 1,2, . . . , k . The following results are proved : then K,, has an (n,, n2,, . , , n,)-chromatic factorization.

We consider only finite, undirected graphs without loops or multiple edges. Our notation and terminology will be standard except as indicated; a good reference for undefined terms is [ 11.

* U Ek be a partition of E ( G ) . De-

📜 SIMILAR VOLUMES

Bounds on chromatic numbers of multiple

Bounds on chromatic numbers of multiple factors of a complete graph

✍ Ján Plesník 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 306 KB 👁 1 views

## Abstract Bounds on the sum and product of the chromatic numbers of __n__ factors of a complete graph of order __p__ are shown to exist. The well‐known theorem of Nordhaus and Gaddum solves the problem for __n__ = 2. Strict lower and some upper bounds for any __n__ and strict upper bounds for __n

Star factorizations of graph products

✍ Darryn E. Bryant; Saad I. El-Zanati; Charles Vanden Eynden 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB 👁 1 views

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

Chromaticity of triangulated graphs

✍ Paul Vaderlind 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

A graph G is called triangulated (or rigid-circuit graph, or chordal graph) if every circuit of G with length greater than 3 has a chord. It can be shown (see, UI, . . . , u,, . Let G = G,.