Gallai colorings and domination in multipartite digraphs

Details Gallai colorings and domination in multipartite digraphs Gallai colorings and domination in multipartite digraphs

2010-06-10

arxiv.org/abs/1006.2044v1

Mathematics

Combinatorics

15 pages, 8 figures

Scientific paper

Assume that D is a digraph without cyclic triangles and its vertices are partitioned into classes A_1,...,A_t of independent vertices. A set $U=\cup_{i\in S} A_i$ is called a dominating set of size |S| if for any vertex $v\in \cup_{i\notin S} A_i$ there is a w in U such that (w,v) is in E(D). Let beta(D) be the cardinality of the largest independent set of D whose vertices are from different partite classes of D. Our main result says that there exists a h=h(beta(D)) such that D has a dominating set of size at most h. This result is applied to settle a problem related to generalized Gallai colorings, edge colorings of graphs without 3-colored triangles.

Affiliated with

Also associated with

No associations

Rating

Gallai colorings and domination in multipartite digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Gallai colorings and domination in multipartite digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Gallai colorings and domination in multipartite digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-492359