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

ABSTRACT:

The subjcct of this paper is a relaxation of proper graphcolorings - bounded monochromatic component colorings (BMC colorings). Avertex- coloring of a graph is called a BMC coloring if every color-classinduces monochromatic components containing at most a certain bounded num­berof vertices. A proper coloring for instance is a BMC coloring in which everycolor-class induces monochromatic components of order one. We investigate threedifferent aspects of BMC colorings. We investigate extremal graph theoretic problems of BMCcolorings. For certain families of graphs we determine bounds for the smallestmonochromatic component, order C, the critical component order, such that everygraph contained in this family accommodates for a BMC col­oring with respect toC. We determine bounds for the critical compo­nent order C for graphs with abounded maximum degree: Every graph of maxfmum degree at most three admits aBMC 2-coloring with one color-class inducing monochromatic components of orderone and the other color-class inducing monochromatic components of order atmost 22; and every graph of maximum degree at most five admits a BMC 2-coloringinducing monochromatic components of order at most 1908 in each of the twocolor-classes. Additionally we restrict, the graphs to being planar and showthat every maximal planar graph (a triangula- tion) with maximum degreeand containing at most, d vertices of odddegree admits a BMC 3-coloring inducing monochromatic components of order at.most To almost all proofs related to BMC colorings there is acommon denominator: bounded component transversals of multipartite graphs. Thuswe devote the first part of this paper to these transversals, prov­ing bothextremal and algorithmic results. We investigate the smallest number ofverticesthat still guarantees the existence of (anefficient algorithm for finding) a transversal inducing bounded components inevery multipartite graph with partite sets of order at leastand maximum degree at most. We further emphasize the importance oftransversals inducing bounded components with an application to the LinearArboricity Conjecture.