The B Chromatic Number And Outer Dommination Number Of Graphs

A b-coloring of a graph G is a proper vertex coloring such that each color classcontains a vertex that has a neighbor in all other color classes. Any such vertex will becalled a b-vertex of color i. The b-chromatic number χb(G) is the largest integer k suchthat G admits a b-coloring with k colors. In this thesis, we disprove two conjecturesposed recently by Jakovac and Peterin (Studia Sci. Math. Hungar.49(2012)156-169)onthe b-chromatic number of strong product and lexicographic products of graphs. Letf(k, g)=min{n|there exists a graph G on n vertices with χb(G)=k and girth at leastg}. We determine the exact value of f(k, g) for the case when g∈{3,4,∞}.A set S of vertices of a graph G is an outer-connected dominating set if every vertexnot in S is adjacent to some vertex in S and the subgraph induced by V\S is connected.The outer-connected domination number γ c(G) is the minimum size of such a set. Wepresent an infnite family of2-connected cubic graphs, in which the number of vertices in alongest path are much less than the half of their orders. This disprove a recent conjectureposed by Akhbari, Hasni, Favaron, Karami, Sheikholeslami (J.Combin. Optim.(2011),DOI:10.1007/s10878-011-9427-x).