The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs

Poppy Immel; Paul S. Wenger

Discussiones Mathematicae Graph Theory (2017)

  • Volume: 37, Issue: 1, page 165-174
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Poppy Immel, and Paul S. Wenger. "The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs." Discussiones Mathematicae Graph Theory 37.1 (2017): 165-174. <http://eudml.org/doc/288067>.

@article{PoppyImmel2017,
abstract = {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.},
author = {Poppy Immel, Paul S. Wenger},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {distinguishing; distinguishing number; list distinguishing; interval graph; list distinguishing number},
language = {eng},
number = {1},
pages = {165-174},
title = {The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs},
url = {http://eudml.org/doc/288067},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Poppy Immel
AU - Paul S. Wenger
TI - The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 1
SP - 165
EP - 174
AB - 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.
LA - eng
KW - distinguishing; distinguishing number; list distinguishing; interval graph; list distinguishing number
UR - http://eudml.org/doc/288067
ER -

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.