Some Results On External Bisections Of Cubic Graphs

Let G =(V, E) be a graph. An external partition of G is a bipartition of V such that each vertex has at least half of its neighbors in the other part. A bisection of V = V, U V2 is a partition with |V1| = |V2|. If ||V1|-|V2|| ≤ 1, then we call it a near-bisection. In 2013, Ban and Linial conjectured that the Petersen graph is the only connected cubic graph that has no external bisection. In 2015, Esperet, Mazzuoccolo and Tarsi [9] presented a family of cubic graphs with more than one bridges that have no external bisection and thus disproved the conjecture of Ban and Linial. Then, Ban and Linial[8] restated their conjecture claiming that the Petersen graph is the only 2-edge connected cubic graph with no external bisection and they believe that every cubic graph with a single bridge has an external bisection. They also showed that every class-1 graph of 3- or 4-regular has an external bisection(a graph is said to be of class-1,if χ’(G)=Δ(G)), We generalize their conclusion and prove that: let G be a graph with Δ(G) ≤ 4, if G has a 2-factor with at most one odd cycle, then G has an external near-bisection.As opposite a similar problem known as internal partition asks a partition of V such that each vertex has at least half of its neighbors in its own part. We know that some graphs have no internal partition. Ban and Linial[8] presented some necessary conclusions for (n - 4)-regular graphs of order n which admit internal partitions. In this thesis, we show the following result: let G be a cubic graph, if G has an external bisection or α(G) ≥ n/2 - 1, then G has an internal partition. Ban and Linial[8] also conjectured that if G is (n - 4)-regular with n vertices and has no internal partition,then G is a disconnected cubic graph that has an odd number of components of which each has no external bisection and all other components have the property that all their external partitions are bisections. Note that each internal bisection of an (n - 4)-regular graph of order n is an external bisection of its complement. We show that for two cubic graphs F and H with H having an external bisection, if F has no internal partition, then (?) has no internal partition. We also discuss the case that F has internal partitions.