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

Citations Over Time

Abstract

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

Related Papers

• → Adjacent Vertex Reducible Vertex-Total Coloring of Graphs(2009)1 cited
• → On $$\alpha $$-Vertex Choosability of Graphs(2020)1 cited
• → Resistance Distance and Kirchhoff Index of Graphs with Pockets(2018)
• → On Coloring of graph fractional powers(2008)
• → Strong domination number of a modified graph(2022)