A Comparative Analysis on Dominating Colour and Bounded Component Transversals of Graphs

Graph Colorings : A graph G is a set V(G) of vertices and a set E(G) of edges, each connecting a pair of vertices, its endpoints. We say that the two endpoints of an edge arc adjacent. A drawing that shows the well known Petersen Graph can be found in Figure 1(a). Figure 1: The Petersen Graph and a proper 3-coloring of its vertices. A proper k-coloring of the vertices of a graph G is an assignment, of k colors (often the integers 1,... ,k) so that no two adjacent, vertices get. the same color, sec for instance Figure 1(b) for a proper 3-coloring of the Petersen Graph. The set of vertices receiving color j is a color-class and induces a graph with no edges, i.e., it is an independent set of G. So, a proper fc-coloring of the vertices of G is simply a partition of V(G) into k independent sets (compare Figure 1(b). Figure 2: A partition of the Petersen Graph into three independent sets. The chromatic numberof a graph G is the minimum k for which there is a ^-coloring of G. One straightforward reason for a graph to have large chromatic number is the containment of a large clique (i.e., a large complete subgraph). Obviously if a graph G contains a clique of order k, then. Similarly for every subgraphit holds that. Since the Petersen Graph contains odd cycles, and an odd cycle requires at least, three colors in any proper coloring, the chromatic number of the Petersen Graph is at. least three. The following proposition states a relation between the maximum degreeof a graph G and its chromatic number. Bounded Component Transversals : Let us recall that a transversal of a multipartite graph is a subset, of its vertices containing exactly one vertex from each partite set. The transversal graph is the graph induced by the vertices of the transversal. For an integerwe call a transversal an f-be transversal if the largest, component of the transversal graph contains at most / vertices. The main goal of this part of the paper is to guarantee the existence of bounded component transversals for multipartite graphs that have large partite sets, with respect to their maximum degree. Moreover we want to elaborate on algorithms that even find such bounded component transversals. It. seems natural that for some fixed maximum degree, the more vertices a multipartite graph contains in each of its partite sets, the more freedom is given to choose a transversal, possibly inducing only small components in the transversal graph. We have seen in Proposition 0.2 that the (list.-)chromatic number of a graph can easily be upper bounded by its maximum degree, independent of the number of vertices contained in the graph. Let. us for a moment focus on independent transversals, i.e., transversals inducing an independent, set. its partite sets is lower-bounded by some valuedepending only on. In contrast to the greedy algorithm for proper (list-)colorings, one can observe that a greedy algorithm for choosing an independent, transversal of G - choose a vertex ti from K that is not adjacent to any of the earlier chosen vertices tj in G, j < i is likely to fail. This algorithm can get. stuck in a partial transversal ti,.. such that every vertex of Vk+i is adjacent to a vertex of £1,..., tk, with k < m. Bounded component, transversals have proved to be very applicable in many areas of graph theory. In this paper we show an application of bounded component, transversals in order to get one tiny step closer to a proof of the Linear Arboricity Conjecture. Bounded Monochromatic Component Colorings Sometimes the number of colors available to color a graph is less than its chromatic number. Therefore one is forced to relax the properness condition and to find a good approximation of its properness. Another good reason to introduce relaxations of proper colorings is that in some theoretical or practical situations a small deviation from proper is still acceptable, while the problem could become tractable, or in certain problems the use of the full strength of proper coloring is an "overkill". Often a weaker concept, suffices and provides better overall results.

Let. G be a multipartite graph with. A transversal T of G is a subset of the vertices in G containing exactly one vertex from each partite set V*. An f-bc transversal of a graph with a vertex partition is a transversal T in which each connected component of the subgraph induced by T (the transversal graph) has at most / vertices. Letdenote the smallest integersuch that there exists an 771-partite graph G with maximum degree A and parts of size n and with no f-bc transversal. We definein case we do not. want to restrict the number of parts in the graphs under consideration and letdenote. It is not hard to check that this limit always exists. Independent Transversals : Historically the investigation ofstarted with 1-bc transversals, subsequently called independent transversals. Independent transversals and in particular the determination of the

andreceived a lot of attention. In a series of workshas been completely determined. Theorem 1.3. For integersandthe following holds, The upper bound for all m and n has been proved by Szabo and Tardos for even m in and in is has been shown that this construction is also optimal for odd in (adding one more partite set). We give here a simplified construction showing for only. This yields a tight bound if n is even. Let G be the graph in Figure 3 (a vertex represents a whole class of vertices). That is, G is an r-partite graph with partite sets of size n,and each partite setis partitioned into two almost equally sized classesand . Let every vertex in partbe adjacent to every vertex in, with and let every vertex inbe adjacent, to every vertex in . We assume that, the two parts Vm-\ and Vm each contain vertices and respectively. Further let every vertex ofbe adjacent to and Figure 3: An ra-partite graph G without an independent transversal. matching transversals. According to Theorem every multipartite graph G with partite sets of order n andcontains a matching transversal. On the other hand according to Proposition there arc multipartite graphs with partite sets of order n and without a matching transversal. We think that these graphs are in some sense optimal. Theorem. Every multipartite graph G with partite sets of order at least two and with maximum degreecontains a match ing transversal T,. Moreover there is a linear-time (in the order of G) algorithm that finds T. We will investigatefor matching transversals (/ = 2). We can construct graphs such that the following holds.

Throughout this paper we restrict ourselves to independent, transversals. We call the running-time of an algorithm with input graph G polynomial if it is polynomial in the order of G, assuming thatis constant. Let G be a multipartite graph with partite sets containing at least n vertices. The goal of this paper is to derive a polynomial-time algorithm that finds an independent transversal of G. In order to do so we are forced to strengthen the condition on the partite set sizes from(for which G is guaranteed to contain an independent transversal according to Theorem 1.1) to. Note here that Alon mentions that a deterministic polynomial-time algorithm exists that finds an independent transversal of G even if only holds, G being a large constant. We believe that in a future work our results can be combined with the techniques of Alon to obtain an algorithm that finds an independent transversal in every multipartite graph G with parts containing at leastmany vertices, for some constantthat is much smaller than the constant G implicitly given in.

Let us recall the definition of BMC colorings. We say that a fc-coloring of a graph is-BMC if every . Note that a (1,..., l)-BMC k-coloring corresponds to a proper ^-coloring. We mainly deal with the two most natural cases of BMC k- colorings. We say C- symmetric BMC k-coloring (also C-sbmc k- c oloring) when. Similarly we say C-asymmetric BMC (k,l)- coloring (also C-ABMC (k, /)-coloring) when C; = 1, forand Cj = C, for. For 2-colorings refer to a C-ABMC (1, l)-coloring also by a C-ABMC 2-coloring. In this part of the paper we investigate BMC colorings of graphs with bounded maximum degree. Symmetric BMC colorings were first studied by Kleinberg, Motwani, Raghavan, and Venkatasubramanianby in. In this paper we focus on BMC 2-colorings. Symmetric BMC 2-colorings have been studied by Alon, Ding, Oporowski, and Vertigan and implicitly, even earlier, by Thomasscn who resolved the problem for the line graph of 3-regular graphs initiated by Akiyama and Chvatal. Asymmetric BMC 2-colorings were first introduced in a joint paper with Tibor Szabo. In this paper we investigate BMC k-colorings of bounded degree (planar) graphs, k > 2. Also Haxell, Szabo, and Tardos in, Linial, Matousek, Shcffct, and Tardos in, and Matousek and Prfvetivy in investigated (symmetric) BMC colorings. Independently Andrews and Jacobson, Harary and Jones, and Cowen, Cowen, and Woodall introduced and investigated the concept of improper colorings over various families of graphs. A ^-coloring is called /-improper if none of the at most k colors induces a monochromatic component containing vertices of degree larger than /. Hcnce in an improper coloring the amount of error is measured in terms of the maximum degree of monochromatic components rather than in terms of their order. Several papers on the topic have since appeared; in particular, two papers, by Eaton and Hull and Skrckovski, have extended the work of Cowen ct al. to a list-coloring variant of improper colorings. Linial and Saks studied low diameter graph decompositions, where the quality of the coloring is measured by the diameter of the monochromatic components. Their goal was to color graphs with as few colors as possible such that each monochromatic connected component has a small diameter. Haxcll, Pikhurko, and Thomason study the fragmentability of graphs introduced by Edwards and Farr, in particular for bounded degree graphs. A graph is called-fragmentable if one can remove a coloring one must remove an independent set and end up with small components. The so-called relaxed chromatic number (sometimes also called generalized chromatic number) was introduced by Weaver and West. They used "relaxation" in a much more general sense than us, requiring that each color-class is the member of a given family of graphs.

In this section we investigate symmetric BMC colorings of planar graphs. Due to the Four Color Theorem we know that every planar graph G admits a proper 4-coloring, hence sbmc4(G?) = 1. On the other hand there are planar graphs which cannot be properly colorcd with only three colors. Moreover for a planar graph G the determination whether G is properly 3-colorablc is NP-complcte, sec Theorem 0.1. Nevertheless the following simple characterization of triangulations that arc properly 3-colorable has been shown by Hcawood. Theorem : The vertices of a triangulation G are properly 3-colorable if and only if G is Eulerian. In contrast to the long and computer aided proof of the Four Color Theorem, and even its simplification by Robertson. Sanders, Seymour, and Thomas, there is a rather compact proof by Cowen, Cowen, and Woodall not assuming the truth of the Four Color Theorem that sbniC4for every planar graph G. As mentioned earlier amongst the many results of, the authors show the existence of planar graphs H\ with arbitrarely many vertices and with maximum degree at most six such that. Linial, Matousek, Shcffct, and Tardos study bounded monochromatic component, colorings of minor closed classes of graphs. They show for instance that for every planar graph G, and they construct planar graphs H2 with . For 3-colorings Kleinberg, Motwani, Raghavan, and Vcnkatasubramanianby in construct planar graphs such that . These graphs have large maximum degree, that is,. Motivated by this they ask for

Theory of domination and graph colouring theory are two important as well as fastest growing areas in combinatorics. A number of variations of domination have been introduced by several authors. In this sequence, Benedict et al. introduced a new variation in domination, namely, chromatic transversal domination which involves both domination and colouring. Also partitioning the vertex set V of a graph G into subsets of V having some property is one direction of research in graph theory. For instance, one such partition is domatic partition which is a partition of V into dominating sets. Analogously, we here demand each set in the partition of V to have the property of chromatic transversal domination instead of just domination and call this partition a chromatic transversal domatic partition. Further, the maximum order of such partition is called the chromatic transversal domatic number which is denoted by dct(G).

• E.J. Cockayne and S.T. Hedetniemi, Towards a Theory of Domination in Graphs, Networks 7 (1977), 247–261.

• F. Harary and K. F. Jones, Conditional colorability, in: Graphs and applications, Boulder Colorado, Wiley-Intersci. Publ., 1982, 127{136.

• K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21, 3 (1977), 491{567.

• L. B. Michaelraj, S. K. Ayyaswamy, and S. Arumugam, Chromatic transversal domination in graphs, J. Combin. Math. Combin. Comput. 75 (2010), 33–40.

• N. Alon, The Strong Chromatic Number of a Graph, RSA: Random Structures & Algorithms 3 (1992), 1{7.

• N. Eaton and T. Hull, Defective list colorings of planar graphs, Bull. Inst. Combin. Appl. 25 (1999), 79{87.

• N. Linial, J. Matou_sek, O. She_et, and G. Tardos, Graph coloring with no large monochromatic components, 2007. Submitted.

• P.D. Seymour, On the two-colouring of hypergraphs, Quart. J. Math. Oxford Ser. (2), 25 (1974), 303–312.

• R. Berke and G. Tardos, On bounded monochromatic component 3-colorings of planar graphs, 2008. In preparation.

• R. Steinberg, The state of the three color problem, Ann. Discrete Math. 55 (1993), 211{248.

 S. K. Ayyaswamy and C. Natarajan, On graphs whose chromatic transversal number is two, Proyecciones 30 (2011), no. 1, 59–64.