Restraints permitting the largest number of colourings

Abstract: A extit{restraint}

r

on

G

is a function which assigns each vertex

v

of

G

a finite set of forbidden colours

r (v)

. A proper colouring

c

of

G

is said to be extit{permitted by the restraint r} if

c (v) o t i n r (v)

for every vertex

v

of

G

. A restraint

r

on a graph

G

with

n

vertices is called a extit{

k

-restraint} if

| r (v) | = k

and

r (v) s u b s e t e q 1, 2, d o t s, k n

for every vertex

v

of

G

. In this article we discuss the following problem: among all

k

-restraints

r

on

G

, which restraints permit the largest number of

x

-colourings for all large enough

x

? We determine such extremal restraints for all bipartite graphs.

Recommendations

Cites Work

Cited In (4)

This page was built for publication: Restraints permitting the largest number of colourings