Premium
Maximum number of colorings of (2 k, k 2 )‐graphs
Author(s) -
Lazebnik Felix,
Pikhurko Oleg,
Woldar Andrew
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20254
Subject(s) - combinatorics , mathematics , lambda , simple graph , graph , vertex (graph theory) , integer (computer science) , discrete mathematics , physics , computer science , optics , programming language
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