✦ LIBER ✦

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

✍ Scribed by Felix Lazebnik; Oleg Pikhurko; Andrew Woldar

Publisher: John Wiley and Sons
Year: 2007
Tongue: English
Weight: 168 KB
Volume: 56
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20254

No coin nor oath required. For personal study only.

✦ Synopsis

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}, \lambda) = {\rm max} {{P}_{G}(\lambda):{G} \in {\cal F}_{{2}{k},{k}^{2}}}$. We prove that $f(2{k}, {k}^{2}, 3) = {P}_{{K}_{{k}, {k}}}(3)$ and ${K}_{{k},{k}}$ is the only extremal graph. We also prove that $f({2}{k}, {k}^{2}, 4) = ({6}+{o}(1)){4}^{k}$ as ${k}\to \infty$. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 135–148, 2007

📜 SIMILAR VOLUMES

Algorithms for maximum k-colorings and k

Algorithms for maximum k-colorings and k-coverings of transitive graphs

✍ Fǎnicǎ Gavril 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 356 KB

Consider a graph G and a positive integer k. The maximum k-coloring problem is to color a maximum number of vertices using k colors, such that no two adjacent vertices have the same color. The maximum k-covering problem is to find k disjoint cliques covering a maximum number of vertices. The present

Total colorings of planar graphs with la

Total colorings of planar graphs with large maximum degree

✍ Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 3 views

It is proved that a planar graph with maximum degree ∆ ≥ 11 has total (vertex-edge) chromatic number ∆ + 1.

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

List Colorings of K5-Minor-Free Graphs W

List Colorings of K5-Minor-Free Graphs With Special List Assignments

✍ Daniel W. Cranston; Anja Pruchnewski; Zsolt Tuza; Margit Voigt 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

The following question was raised by Bruce Richter. Let G be a planar, 3-connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L-list colorable for every list assignment L with |L(v)|=min{d(v), 6} for all v ∈ V (G)? More generally, we ask for which pairs (r, k)

Circumferences of k-connected graphs inv

Circumferences of k-connected graphs involving independence numbers

✍ Guantao Chen; Zhiquan Hu; Yaping Wu 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 211 KB 👁 1 views

Let G be a k-connected graph of order n, := (G) the independence number of G, and c(G) the circumference of G. Chvátal and Erdo ˝s proved that if ≤ k then G is hamiltonian. For ≥ k ≥ 2, Fouquet and Jolivet in 1978 made the conjecture that c(G) ≥ k(n+ -k) / . Fournier proved that the conjecture is tr

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