✦ LIBER ✦

Highly irregular m-chromatic graphs

✍ Scribed by Yousef Alavi; Fred Buckley; Marc Shamula; Sergio Ruiz

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 620 KB
Volume: 72
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90188-4

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is highly irregular if it is connected and the neighbors of each vertex have distinct degrees.

In this paper, we study existence and extremal problems for highly irregular graphs with a given maximum degree and focus our attention on highly irregular graphs that are m-chromatic for m 3 2.

📜 SIMILAR VOLUMES

Highly irregular graphs

✍ Yousef Alavi; Gary Chartrand; F. R. K. Chung; Paul Erdös; R. L. Graham; Ortrud R 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 531 KB

A connected graph is highly irregular if each of its vertices is adjacent only to vertices with distinct degrees. In this paper w e investigate several problems concerning the existence and enumeration of highly irregular graphs as well as their independence numbers, with particular focus on the cor

Highly irregular graphs with extreme num

Highly irregular graphs with extreme numbers of edges

✍ Zofia Majcher; Jerzy Michael 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 219 KB

A simple connected graph is highly irregular if each of its vertices is adjacent only to vertices with distinct degrees. In this paper we find: (1) the greatest number of edges of a highly irregular graph with n vertices, where n is an odd integer (for n even this number is given in [1]), (2) the sm

On the chromatic number of certain highl

On the chromatic number of certain highly symmetric graphs

✍ P.P Pálfy 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 470 KB

Regularizing irregular graphs

✍ Fred Buckley 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 348 KB

Ahypergraph-free construction of highly

Ahypergraph-free construction of highly chromatic graphs without short cycles

✍ Igor Kříž 📂 Article 📅 1989 🏛 Springer-Verlag 🌐 English ⚖ 128 KB

4-chromatic projective graphs

✍ Youngs, D. A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 464 KB

We construct a family of 4-chromatic graphs which embed on the projective plane, and characterize the edge-critical members. The family includes many well known graphs, and also a new sequence of graphs, which serve to improve Gallai's bound on the length of the shortest odd circuit in a 4-chromatic