The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs

• Autorzy: Poppy Immel , Paul S. Wenger
• Języki publikacji: EN

Abstrakty

EN

A 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 distinguishing number of G is the minimum k such that G has a distinguishing coloring where each vertex is assigned a color from {1, . . . , k}. A list assignment to G is an assignment L = {L(v)}v∈V (G) of lists of colors to the vertices of G. A distinguishing L-coloring of G is a distinguishing coloring of G where the color of each vertex v comes from L(v). The list distinguishing number of G is the minimum k such that every list assignment to G in which |L(v)| = k for all v ∈ 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.

Słowa kluczowe

EN

distinguishing; distinguishing number; list distinguishing; interval graph

Kategorie tematyczne

• 05C60: Isomorphism problems (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 1
• Strony: 165-174

Daty

wydano

2017-02-01

otrzymano

2015-09-15

poprawiono

2016-03-23

zaakceptowano

2016-03-23

online

2017-01-13

Twórcy

autor

Poppy Immel

• School of Mathematical Sciences, Rochester Institute of Technology, Rochester, NY,

autor

Paul S. Wenger

• School of Mathematical Sciences, Rochester Institute of Technology, Rochester, NY,

Identyfikatory

DOI

10.7151/dmgt.1927