Maximizing H‐Colorings of Connected Graphs with Fixed Minimum Degree

Abstract: For graphs

G

and

H

, an

H

-coloring of

G

is a map from the vertices of

G

to the vertices of

H

that preserves edge adjacency. We consider the following extremal enumerative question: for a given

H

, which connected

n

-vertex graph with minimum degree

d e l t a

maximizes the number of

H

-colorings? We show that for non-regular

H

and sufficiently large

n

, the complete bipartite graph

K_{d e l t a, n - d e l t a}

is the unique maximizer. As a corollary, for non-regular

H

and sufficiently large

n

the graph

K_{k, n - k}

is the unique

k

-connected graph that maximizes the number of

H

-colorings among all

k

-connected graphs. Finally, we show that this conclusion does not hold for all regular

H

by exhibiting a connected

n

-vertex graph with minimum degree

d e l t a

which has more

K_{q}

-colorings (for sufficiently large

q

and

n

) than

K_{d e l t a, n - d e l t a}

.

Recommendations

Cites Work

Cited In (9)

This page was built for publication: Maximizing H‐Colorings of Connected Graphs with Fixed Minimum Degree