A graph G is a union of two planar graphs Prove that chiG ge

A graph G is a union of two planar graphs. Prove that chi(G) ge 12.

Solution

Assume G is a union of two graph and with a minimum number of vertices (nn). We may also assume that we have maximized the number of edges .So G has minimum degree >=3 and d(u)+d(v)>13d(u)+d(v)>13 for every edge . The edge maximization impliesfor any non adjacent u and v with

d(u)+d(v)>13, then (G+uv) can be considered as non-planar

Now we give a charge to each vertex: a vertex v gets charge 6d(v).Implementing the theory e3n6 (equality is true in case of triangulations)

we find the total charge v(6d(v))=6n2e6n(6n12)=12.

Now we discharge: a vertex v with a +ve charge distributes its charge uniformly among its neighbours. We apply this for vertices simultaneously.

Since no charge is lost, there must still be vertices with a +ve charge.

Let v be a vertex with a +ve charge.

Case 1: d(v) is less or equal to 8d. Since a vertex can only obtain a positive charge from a neighboring vertex u with degree at most 5, we find an edge uv with d(u)+d(v) is less or equal to 13d. Contradiction.

Case 2: d(v)=9. v has no neighbours of degree 3 or 4, so its +ve charge can only be obtained from neighbours of degree 5 and each of them contributes a charge of 15 (they started with charge 1 and sent an equal part, i.e. 15 to each of their neighbours). Since v started out with charge 3 it would need 16 neighbours to end up with a +ve charge. Contradiction.

Case 3: d(v)=10. As we have seen in case of 2: no neighbours of degree 3, and each neighbour of degree 4 or 5 contributes at most charge 12. Since v started with charge 4, it needs at least 9 neighbours of degree 4 or 5. Let v1,…,v10 be the neighbours of v, arranged clockwise. Without loss of generality we may assume that v1 and v2 both have degree 4 or 5. Since v1 and v2 cannot be adjacent (since d(v1)+d(v2)10, the face having

,v1,v2v, contains at least one other neighbour u of v1. This neighbour must have degree at least 9 .

d(v1)+d(u)13.

But now we have non-adjacentu,v that are on the same face, so G+uv is planar and d(u)+d(v)>13.

Contradiction.

Case 4: d(v)11. Each neighbour of degree <6 contributes at most 1. vv starts with charge 6d(v)

, so it needs at least d(v)5 neighbours of degree less than 6 to end up with a positive charge.

Since d(v)5>(d(v)/2) we again must find two consecutive neighbours of low degree and, like in case 3, these must either be adjacent or expose a high-degree neighbour that can be connected to vv without breaking planarity. This final contradiction finishes the proof.

So in case of union of two planar graph , X(G)<=12(proved)