✦ LIBER ✦

Regular graphs with prescribed chromatic number

✍ Scribed by L. Caccetta; N. J. Pullman

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 200 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140107

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We determine the minimum number of edges in a regular connected graph on n vertices, containing a complete subgraph of order k ≤ n/2. This enables us to confirm and strengthen a conjecture of P. Erdös on the existence of regular graphs with prescribed chromatic number.

📜 SIMILAR VOLUMES

Smallest regular graphs with prescribed

Smallest regular graphs with prescribed odd girth

✍ Guo-Hui Zhang 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 484 KB 👁 1 views

## Abstract The odd girth of a graph __G__ gives the length of a shortest odd cycle in __G.__ Let __f(k,g)__ denote the smallest __n__ such that there exists a __k__‐regular graph of order __n__ and odd girth __g.__ The exact values of __f(k,g)__ are determined if one of the following holds: __k__

Extremal Regular Graphs with Prescribed

Extremal Regular Graphs with Prescribed Odd Girth

✍ G.H. Zhang 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 496 KB

The odd girth of a graph \(G\) gives the length of a shortest odd cycle in \(G\). Let \(f(k, g)\) denote the smallest \(n\) such that there exists a \(k\)-regular graph of order \(n\) and odd girth \(g\). It is known that \(f(k, g) \geqslant k g / 2\) and that \(f(k, g)=k g / 2\) if \(k\) is even. T

The generalized acyclic edge chromatic n

The generalized acyclic edge chromatic number of random regular graphs

✍ Stefanie Gerke; Catherine Greenhill; Nicholas Wormald 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB 👁 1 views

## Abstract The __r__‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle __C__ has at least min(|__C__|, __r__) colors. We show that (__r__ − 2)__d

Distance Graphs with Finite Chromatic Nu

Distance Graphs with Finite Chromatic Number

✍ I.Z. Ruzsa; Zs. Tuza; M. Voigt 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 96 KB

The distance graph G(D) with distance set D={d 1 , d 2 , ...} has the set Z of integers as vertex set, with two vertices i, j ¥ Z adjacent if and only if |i -j| ¥ D. We prove that the chromatic number of G(D) is finite whenever inf{d i+1 /d i } > 1 and that every growth speed smaller than this admit

On the chromatic number of a random 5-re

On the chromatic number of a random 5-regular graph

✍ J. Díaz; A. C. Kaporis; G. D. Kemkes; L. M. Kirousis; X. Pérez; N. Wormald 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB 👁 1 views

## Abstract It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is as

Path chromatic numbers of graphs

✍ Jin Akiyama; Hiroshi Era; Severino V. Gervacio; Mamoru Watanabe 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB