✦ LIBER ✦

Graphs with least number of colorings

✍ Scribed by A. Sakaloglu; A. Satyanarayana

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 535 KB
Volume: 19
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190190407

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A λ‐coloring of a graph G is an assignment of λ or fewer colors to the points of G so that no two adjacent points have the same color. Let Ω (n,e) be the collection of all connected n‐point and e‐edge graphs and let Ωp(n,e) be the planar graphs of Ω(n, e). This paper characterizes the graphs that minimize the number of λ‐colorings in Ω(n, e) for all λ > 1 and Ωp(n,e) for all λ.4. © 1995 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Maximum number of colorings of (2k, k2)-

Maximum number of colorings of (2k, k2)-graphs

✍ Felix Lazebnik; Oleg Pikhurko; Andrew Woldar 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

## Abstract Let ${\cal F}\_{{2}{k},{k}^{2}}$ consist of all simple graphs on 2__k__ vertices and ${k}^{2}$ edges. For a simple graph __G__ and a positive integer $\lambda$, let ${P}\_{G}(\lambda)$ denote the number of proper vertex colorings of __G__ in at most $\lambda$ colors, and let $f(2k, k^{2

Minimal Graphs with Crossing Number at L

Minimal Graphs with Crossing Number at Least k

✍ R.B. Richter; C. Thomassen 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 277 KB

The number of defective colorings of gra

The number of defective colorings of graphs on surfaces

✍ Tom Rackham 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB 👁 1 views

A (k, 1)-coloring of a graph is a vertex-coloring with k colors such that each vertex is permitted at most 1 neighbor of the same color. We show that every planar graph has at least c n distinct (4, 1)-colorings, where c is constant and ≈ 1.466 satisfies 3 = 2 +1. On the other hand for any >0, we gi

On the Number of 3-Edge Colorings of Cub

On the Number of 3-Edge Colorings of Cubic Graphs

✍ Christian Szegedy 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 127 KB

In this paper we present a short algebraic proof for a generalization of a formula of R. Penrose, Some applications of negative dimensional tensors, in: Combinatorial Mathematics and its Applications Welsh (ed.), Academic Press, 1971, pp. 221-244 on the number of 3-edge colorings of a plane cubic gr

Graphs with unique Ramsey colorings

✍ Jerrold W. Grossman 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 313 KB

Partition graphs and coloring numbers of

Partition graphs and coloring numbers of a graph

✍ E. Sampathkumar; V.N. Bhave 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 288 KB