TAILIEUCHUNG - On dominated coloring of graphs and some Nordhaus-Gaddum-type relations

The minimum number of colors needed for a dominated coloring of G is called the dominated chromatic number of G, denoted by χdom (G). In this paper, dominated coloring of graphs is compared with (open) packing number of G and it is shown that if G is a graph of order n with diam(G) ≥ 3, then χdom(G) ≤ n − ρ(G) and if ρ0(G) = 2n/3, then χdom(G) = ρ0(G). | Turk J Math (2018) 42: 2148 – 2156 © TÜBİTAK doi: Turkish Journal of Mathematics Research Article On dominated coloring of graphs and some Nordhaus–Gaddum-type relations Fatemeh CHOOPANI1 ,, Abbas JAFARZADEH1,∗,, Ahmad ERFANIAN1 ,, Doost Ali MOJDEH2 , 1 Department of Pure Mathematics, Ferdowsi University of Mashhad, Mashhad, Iran 2 Department of Mathematics, University of Mazandaran, Babolsar, Iran Received: • Accepted/Published Online: • Final Version: Abstract: The dominated coloring of a graph G is a proper coloring of G such that each color class is dominated by at least one vertex. The minimum number of colors needed for a dominated coloring of G is called the dominated chromatic number of G , denoted by χdom (G) . In this paper, dominated coloring of graphs is compared with (open) packing number of G and it is shown that if G is a graph of order n with diam(G) ≥ 3 , then χdom (G) ≤ n − ρ(G) and if ρ0 (G) = 2n/3 , then χdom (G) = ρ0 (G) , and if ρ(G) = n/2 , then χdom (G) = ρ(G) . The dominated chromatic numbers of the corona of two graphs are investigated and it is shown that if µ(G) is the Mycielsky graph of G , then we have χdom (µ(G)) = χdom (G) + 1 . It is also proved that the Vizing-type conjecture holds for dominated colorings of the direct product of two graphs. Finally we obtain some Nordhaus–Gaddum-type results for the dominated chromatic number χdom (G) . Key words: Dominated coloring, dominated chromatic number, total domination number 1. Introduction Let G = (V, E) be a simple, undirected, and finite graph. A set D ⊆ V is called a dominating set if the vertices in D dominate all the vertices in V \ D . The domination number of G is the smallest cardinality of a dominating set in G , denoted by γ(G) . For a graph G with no isolated vertices, a dominating set D is called a total dominating set provided that each vertex in V is adjacent to a vertex in D

• Toán học
• Dominated coloring
• Dominated chromatic number
• Total domination number
• Total dominating sets
• Dominated chromatic number χdom(G)