The list distinguishing number equals the distinguishing number for interval graphs

Abstract: A extit{distinguishing coloring} of a graph

G

is a coloring of the vertices so that every nontrivial automorphism of

G

maps some vertex to a vertex with a different color. The extit{distinguishing number} of

G

is the minimum

k

such that

G

has a distinguishing coloring where each vertex is assigned a color from

1, l d o t s, k

. A extit{list assignment} to

G

is an assignment

L = {L (v)}_{v i n V (G)}

of lists of colors to the vertices of

G

. A extit{distinguishing

L

-coloring} of

G

is a distinguishing coloring of

G

where the color of each vertex

v

comes from

L (v)

. The {it list distinguishing number} of

G

is the minimum

k

such that every list assignment to

G

in which

| L (v) | = k

for all

v i n V (G)

yields a distinguishing

L

-coloring of

G

. We prove that if

G

is an interval graph, then its distinguishing number and list distinguishing number are equal.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: The list distinguishing number equals the distinguishing number for interval graphs