Leírás
Speaker: Amitayu Banerjee
Title: New upper bounds of the list distinguishing numbers and the list distinguishing chromatic numbers for infinite connected graphs in ZFC and ZF.
Abstract:
History:
In 1977, László Babai introduced distinguishing vertex colorings under the name asymmetric colorings.
In 1996, Albertson and Collins studied the distinguishing number of a graph.
In 2011, Ferrara et al. extended the notion of a distinguishing vertex coloring to a list distinguishing vertex coloring, and introduced the notion of the list distinguishing number.
In 2006, Collins and Trenk studied distinguishing proper vertex colorings of a graph, and introduced the distinguishing chromatic number of a graph.
In 2013, Ferrara et al. extended the notion of a distinguishing proper vertex coloring to a list distinguishing proper vertex coloring, and introduced the notion of the list distinguishing chromatic number.
Known results in ZFC:
In 2007, Imrich, Klavzar, and Trofimov proved that if G is a connected, infinite graph where the maximum degree Delta of G is an arbitrary cardinal, then the distinguishing number D(G) of G is at most Delta.
In 2017, Imrich et al. proved that if G is a connected infinite graph with a finite maximum degree Delta, then the distinguishing chromatic number chi_{D}(G) is at most 2*Delta-1.
It is known that the distinguishing number D(G) of any graph G is less than or equal to the list distinguishing number D_{L}(G) of G. Analogously, distinguishing chromatic number of G is less or equal to the list distinguishing chromatic number of G.
We prove the following:
1. If G is a connected, infinite graph where Delta is an arbitrary cardinal, then the list distinguishing number D_{L}(G) of G is at most Delta in ZFC.
2. The statement ``if G is a connected, infinite graph where Delta is an arbitrary cardinal, then the list distinguishing number D_{L}(G) of G is at most Delta'' fails in ZF.
3. If G is a connected, infinite graph where Delta is an arbitrary cardinal, then the list distinguishing chromatic number \chi_{D_{L}}(G) of G is at most 2*Delta -1 in ZFC.
4. The statement ``if G is a connected, infinite graph where Delta is an arbitrary cardinal, then the list distinguishing chromatic number D_{L}(G) of G is at most 2*Delta -1'' fails in ZF.