Number of distinguishing colorings and partitions Ahmadi, Bahman; Alinaghipour, Fatemeh; Shekarriz, Mohammad Hadi
Discrete mathematics,
September 2020, 2020-09-00, Letnik:
343, Številka:
9
Journal Article
Recenzirano
Odprti dostop
A vertex coloring of a graph G is called distinguishing (or symmetry breaking) if no non-identity automorphism of G preserves it, and the distinguishing number, shown by D(G), is the smallest number ...of colors required for such a coloring. This paper is about counting non-equivalent distinguishing colorings of graphs with k colors. A parameter, namely Φk(G), which is the number of non-equivalent distinguishing colorings of a graph G with at most k colors, is shown here to have an application in calculating the distinguishing number of the lexicographic product and the X-join of graphs. We study this index (and some other similar indices) which is generally difficult to calculate. Then, we show that if one knows the distinguishing threshold of a graph G, which is the smallest number of colors θ(G) so that, for k≥θ(G), every k-coloring of G is distinguishing, then, in some special cases, counting the number of distinguishing colorings with k colors is very easy. We calculate θ(G) for some classes of graphs including the Kneser graph K(n,2). We then turn to vertex partitioning by studying the distinguishing coloring partition of a graph G; a partition of vertices of G which induces a distinguishing coloring for G. There, we introduce Ψk(G) as the number of non-equivalent distinguishing coloring partitions with at most k cells, which is a generalization to its distinguishing coloring counterpart.
Let G=(V,E) be a simple graph and ϕ:E(G)→{1,2,…,k} be a proper k-edge coloring of G. We say that ϕ is neighbor sum (set) distinguishing if for each edge uv∈E(G), the sum (set) of colors taken on the ...edges incident with u is different from the sum (set) of colors taken on the edges incident with v. The smallest k such that G has a neighbor sum (set) distinguishing k-edge coloring is called the neighbor sum (set) distinguishing index of G and denoted by χ∑′(G) (χa′(G)). It was conjectured that if G is a connected graph and G∉{K2,C5}, then χ∑′(G)≤Δ(G)+2 and χa′(G)≤Δ(G)+2. For a given graph G, let (Le)e∈E be a set of lists of real numbers and each list has size k. The smallest k such that for any specified collection of such lists there exists a neighbor sum (set) distinguishing edge coloring using colors from Le for each e∈E is called the list neighbor sum (set) distinguishing index of G, and denoted by ch∑′(G)(cha′(G)). In this paper, we prove that if G is a planar graph with Δ(G)≥22 and with no isolated edges, then ch∑′(G)≤Δ(G)+6 and cha′(G)≤Δ(G)+3. This improves a result by Przybyło and Wong (Przybyło and Wong, 2015), which states that if G is a planar graph without isolated edges, then ch∑′(G)≤Δ(G)+13 (so cha′(G)≤Δ(G)+13 also holds). Our approach is based on the Combinatorial Nullstellensatz and the discharging method.
On the Total Set Chromatic Number of Graphs Tolentino, Mark Anthony C; Eugenio, Gerone Russel; Ruiz, Mari-Jo
Theory and applications of graphs (Statesboro, Ga.),
07/2022, Letnik:
9, Številka:
2
Journal Article
Recenzirano
Odprti dostop
Given a vertex coloring c of a graph, the neighborhood color set of a vertex is defined to be the set of all of its neighbors’ colors. The coloring c is called a set coloring if any two adjacent ...vertices have different neighborhood color sets. The set chromatic number χs(G) of a graph G is the minimum number of colors required in a set coloring of G. In this work, we investigate a total analog of set colorings; that is, we study set colorings of the total graph of graphs. Given a graph G = (V, E), its total graph T(G) is the graph whose vertex set is V ∪ E and in which two vertices are adjacent if and only if their corresponding elements in G are adjacent or incident. First, we establish sharp bounds for the set chromatic number of the total graph of a graph. Furthermore, we study the set colorings of the total graph of different families of graphs.
An edge-coloring of a graph is called asymmetric if the only automorphism which preserves it is the identity. Lehner, Pilśniak, and Stawiski proved that all connected, locally finite, regular graphs ...except K2 admit an asymmetric edge-coloring with three colors. We generalize this result for graphs whose minimum degree δ and finite maximum degree Δ satisfy δ≥Δ/2.
Distinguishing threshold of graphs Shekarriz, Mohammad H.; Ahmadi, Bahman; Talebpour, S. A. ...
Journal of graph theory,
June 2023, 2023-06-00, 20230601, Letnik:
103, Številka:
2
Journal Article
Recenzirano
Odprti dostop
A vertex coloring of a graph G $G$ is called distinguishing if no nonidentity automorphisms of G $G$ can preserve it. The distinguishing number of G $G$, denoted by D
(
G
) $D(G)$, is the minimum ...number of colors required for such a coloring, and the distinguishing threshold of G $G$, denoted by θ
(
G
) $\theta (G)$, is the minimum number k $k$ such that every k $k$‐coloring of G $G$ is distinguishing. As an alternative definition, θ
(
G
) $\theta (G)$ is one more than the maximum number of cycles in the cycle decomposition of automorphisms of G $G$. In this paper, we characterize θ
(
G
) $\theta (G)$ when G $G$ is disconnected. Afterwards, we prove that, although for every positive integer k
≠
2 $k\ne 2$ there are infinitely many graphs whose distinguishing thresholds are equal to k $k$, we have θ
(
G
)
=
2 $\theta (G)=2$ if and only if ∣
V
(
G
)
∣
=
2 $| V(G)| =2$. Moreover, we show that if θ
(
G
)
=
3 $\theta (G)=3$, then either G $G$ is isomorphic to one of the four graphs on three vertices or it is of order 2
p $2p$, where p
≠
3
,
5 $p\ne 3,5$ is a prime number. Furthermore, we prove that θ
(
G
)
=
D
(
G
) $\theta (G)=D(G)$ if and only if G $G$ is asymmetric, K
n ${K}_{n}$ or K
n
¯ $\bar{{K}_{n}}$. Finally, we consider all generalized Johnson graphs, J
(
n
,
k
,
i
) $J(n,k,i)$, which are the graphs on all k $k$‐subsets of {
1
,
…
,
n
} $\{1,\ldots ,n\}$ where two vertices A $A$ and B $B$ are adjacent if ∣
A
∩
B
∣
=
k
−
i $| A\cap B| =k-i$. After studying their automorphism groups and distinguishing numbers, we calculate their distinguishing thresholds as θ
(
J
(
n
,
k
,
i
)
)
=
n
k
−
n
−
2
k
−
1
+
1 $\theta (J(n,k,i))=\left(\genfrac{}{}{0ex}{}{n}{k}\right)-\left(\genfrac{}{}{0ex}{}{n-2}{k-1}\right)+1$, unless k
=
n
2 $k=\frac{n}{2}$ and i
∈
{
k
2
,
k
} $i\in \{\frac{k}{2},k\}$ in which case we have θ
(
J
(
n
,
k
,
i
)
)
=
n
k $\theta (J(n,k,i))=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.
List distinguishing parameters of trees Ferrara, Michael; Gethner, Ellen; Hartke, Stephen G. ...
Discrete Applied Mathematics,
04/2013, Letnik:
161, Številka:
6
Journal Article
Recenzirano
Odprti dostop
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, χ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∈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)∈L(v) for all v. The list distinguishing number of G, Dℓ(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 χDℓ(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ℓ(T)=D(T), χD(T)=χDℓ(T), and χD(T)≤D(T)+1.
A vertex coloring is called distinguishing if the identity is the only automorphism that can preserve it. The distinguishing threshold θ(G) of a graph G is the minimum number of colors k required ...that any arbitrary k-coloring of G is distinguishing. In this paper, we calculate the distinguishing threshold of a Cartesian product graph. Moreover, we calculate the number of non-equivalent distinguishing colorings of grids.
A proper
-total coloring
of a graph
is a proper total coloring
of
using colors of the set
=
1, 2, . . . ,
. Let
) denote the product of the color on a vertex
and colors on all the edges incident ...with
. For each edge
∈
), if
) ≠
), then we say the coloring
distinguishes adjacent vertices by product and call it a neighbor product distinguishing
-total coloring of
. By
∏(
), we denote the smallest value of
in such a coloring of
. It has been conjectured by Li
that Δ(
) + 3 colors enable the existence of a neighbor product distinguishing total coloring. In this paper, by applying the Combinatorial Nullstellensatz, we obtain that the conjecture holds for planar graph with Δ(
) ≥ 10. Moreover, for planar graph
with Δ(
) ≥ 11, it is neighbor product distinguishing (Δ(
) + 2)-total colorable, and the upper bound Δ(
) + 2 is tight.
A proper k-edge coloring of a graph G is a proper edge coloring of G using colors from k={1,2,…,k}. A neighbor sum distinguishing k-edge coloring of G is a proper k-edge coloring of G such that for ...each edge uv∈E(G), the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. By nsdi(G), we denote the smallest value k in such a coloring of G. It was conjectured by Flandrin et al. that if G is a connected graph without isolated edges and G≠C5, then nsdi(G)≤Δ(G)+2. In this paper, we show that if G is a planar graph without isolated edges, then nsdi(G)≤max{Δ(G)+10,25}, which improves the previous bound (max{2Δ(G)+1,25}) due to Dong and Wang.
We consider a proper coloring
c
of edges and vertices in a simple graph and the sum
f
(
v
) of colors of all the edges incident to
v
and the color of a vertex
v
. We say that a coloring
c
...distinguishes adjacent vertices by sums, if every two adjacent vertices have different values of
f
. We conjecture that
Δ
+
3
colors suffice to distinguish adjacent vertices in any simple graph. In this paper we show that this holds for complete graphs, cycles, bipartite graphs, cubic graphs and graphs with maximum degree at most three.
PDF
