List distinguishing parameters of trees

DOI10.1016/J.DAM.2012.10.003zbMATH Open1262.05050arXiv1111.4989OpenAlexW2135702725MaRDI QIDQ1946232FDOQ1946232

Derrick Stolee, Stephen G. Hartke, Michael Ferrara, Paul S. Wenger, Ellen Gethner

Publication date: 18 April 2013

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A coloring of the vertices of a graph G is said to be distinguishing} provided no nontrivial automorphism of G preserves all of the vertex colors. The distinguishing number of G, D(G), is the minimum number of colors in a distinguishing coloring of G. The distinguishing chromatic number of G, chi_D(G), is the minimum number of colors in a distinguishing coloring of G that is also a proper coloring. Recently the notion of a distinguishing coloring was extended to that of a list distinguishing coloring. Given an assignment L= {L(v) : v in V(G)} of lists of available colors to the vertices of G, we say that G is (properly) L-distinguishable if there is a (proper) distinguishing coloring f of G such that f(v) is in L(v) for all v. The list distinguishing number of G, D_l(G), is the minimum integer k such that G is L-distinguishable for any list assignment L with |L(v)| = k for all v. Similarly, the list distinguishing chromatic number of G, denoted chi_{D_l}(G) is the minimum integer k such that G is properly L-distinguishable for any list assignment L with |L(v)| = k for all v. In this paper, we study these distinguishing parameters for trees, and in particular extend an enumerative technique of Cheng to show that for any tree T, D_l(T) = D(T), chi_D(T)=chi_{D_l}(T), and chi_D(T) <= D(T) + 1.

Full work available at URL: https://arxiv.org/abs/1111.4989

Recommendations

• List-distinguishing colorings of graphs
• The distinguishing chromatic number
• Distinguishability of locally finite trees
• The list distinguishing number equals the distinguishing number for interval graphs
• Trees with distinguishing number two

zbMATH Keywords

distinguishing chromatic numberdistinguishing coloringlist distinguishing chromatic numberlist distinguishing coloringproper distinguishing coloring

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Cited In (6)

• Title not available (Why is that?)
• The distinguishing chromatic number
• Distinguishability of locally finite trees
• The list distinguishing number equals the distinguishing number for interval graphs
• The list distinguishing number of Kneser graphs
• List-distinguishing Cartesian products of cliques

This page was built for publication: List distinguishing parameters of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1946232)