Planarity and Coloring

Planar Graphs:

A graph G is called planar graph if G can be drawn in the plan so that no two of its
edges cross each other.

Non Planar graph: A graph that is not planar is called non planar graph

Plane graph:
A graph G is called a plane graph if it is drawn in the plane so that no two edges of
G cross.

Regions of graphs/faces: A plane graph divides the plane into connected pieces
called regions.
If G is a connected simple plane graph with at least three edges, then the
boundary of every region of G has at least three edges.

Proof:
First if G is tree,
Then order is n
Edges is m=n-1
Then number of region r=1
So n-m+r= n-(n-1)+1
=1+1
=2 equality holds.
So we can only be concerned if G is not a tree.

Assume to the contrary , G is a connected plane graph of minimum size m such

that n-m+r ≠2.
If G is connected and not a tree then G has a cycle with edge e.
Thus G-e is connected plane graph of order n, size m-1 and having a region r-1
So n-(m-1)+(r-1)=2
n-m+1+r-1=2
n-m+r=2
Which is a contradiction.
Therefore, G is a connected plane graph of order n, size m and region r such that
n-m+r = 2.

Proof:
First, suppose that G is connected. If G=P3(Path graph of order 3), then the
inequality holds.
So we can assume that G has at least three edges.
Draw G as a plane graph where G has regions denoted by R1,R2…Rr.
The number of edges of the boundary of Ri are m1,m2…mr.
The boundary of each region contains at least three edges.

​ ​ ​ ​
​ ​ ​ ​ 3r≤ 𝑀 —--------(1)
The number of M counts an edges twice if edges lies on the cycle.
So M ≤ 2m —-----(2)
From 1 and 2 3r ≤ M ≤ 2m.
So 3r ≤ 2m. Apply the Eulur identity
n-m+r=2
3n-3m+3r=6
6 ≤3n-3m+2m
6 ≤3n-m
m ≤ 3n-6 ( Add m on both sides and minus 6 on both sides)

Hence Proved
Proof: Try it on your own

Proof: Try it on your own

Maximal Planer:

Proof:
We proceed by contradiction. Suppose 𝐾3,3 is planar.
The graph has n=6,m=9.
Using Euler formula 6-9+r=2 from this r=5.
Let B be the number of boundaries surrounding these 5 regions. Since each edge is
used as a boundary twice.
We have B=2m
Also, since each region is surrounded by 4 or more boundaries. B≥4r
We know this is true because 𝐾3,3 is bipartite, so does not contain any 3- edge
cycles since no two edges are adjacent.
Thus 4r≤2m. But with r=5 and m=9 this would say that 20≤18
Which is clearly false. Thus 𝐾3,3 is not planar.

Sub Divisions of graphs:

Solu:
Step 1: Check edges are crossing (Not only enough)
Step 2: Check m<=3n-6 (Not only enough)
Step 3: A graph is non planar, if it contains k5 or k3,3
So Check for K5 subdivisions.

Check for K3,3 subdivisions.

A sub division of K3,3 is a subgraph of G. Therefore the given graph is

non-planar.

Graph Coloring

The coloring problem is important in graph theory because it models many

resource-allocation and conflict-avoidance problems. In these problems, certain
items cannot occur simultaneously, so they must be assigned different resources
(colors).

Graph coloring helps solve real-world problems where conflicting tasks must be
assigned different resources while minimizing the total resources used.

In graph terms:

●​ Vertices → objects/tasks/resources​

●​ Edges → conflict or restriction​

 ●​ Colors → available resources​

A proper coloring ensures that conflicting items do not receive the same resource.

Example:

In a college, many courses must conduct exams.​

Some students take multiple courses, so those exams cannot be scheduled at the
same time.

Goal:

●​ Create an exam timetable​

●​ Ensure no student has two exams at the same time​

●​ Use minimum number of time slots​

This is exactly a graph coloring problem.

10.2 Vertex Coloring

Vertex coloring of graph G means an assignment of colors to the vertices of G, one
color to each vertex, such that adjacent vertices are colored differently.

Chromatic Number:

The smallest number of colors in any coloring of graph G is called the chromatic
number of G. Denoted by χ(𝐺).
Note:

1.​ If G is complete then χ(𝐾𝑛) = 𝑛.

Ex, 𝐾5need 5 colors

2.​ If G is cyclic then

χ(𝐶𝑛) = 2 𝑤ℎ𝑒𝑟𝑒 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛; χ(𝐶𝑛) = 3 𝑤ℎ𝑒𝑟𝑒 𝑛 𝑖𝑠 𝑜𝑑𝑑.

Example 1:

Find the chromatic number of graph G?

Solution:

Note:
 Independent Set:

Maximum independent set α(𝐺):

Among all the independent sets, the one having the largest number of
vertices is called a maximum independent set.

Clique/ complete subgraph:

If G is a graph and S is a sub graph of G then S is complete.

1- vertex clique, 3- vertex clique, 4- vertex clique.

Denoted by ω(𝐺).

Proof:

χ(G) = chromatic number​

ω(G) = size of largest clique​

α(G) = size of maximum independent set​

n= number of vertices

First result: χ(G)≥ω(G)

Let H be a clique in G with size ∣H∣=ω(G)

A clique means every pair of vertices is adjacent.

Since every vertex in a clique is adjacent to every other vertex, each vertex must
receive a different color.

Therefore χ(H)=ω(G)-----(1)

because we need exactly that many colors.

Since H is a subgraph of G, the chromatic number of H cannot exceed that of G.

χ(H)≤χ(G)

Sub (1) we get χ(G)≥ω(G)

Second result: χ(G)≥α(G)/n

Let χ(G)=k This means the graph can be colored with k colors.

In vertex coloring, each color class forms an independent set.

So the vertices can be divided into V1,V2,V3,…,Vk

where each Vi is an independent set.

The total number of vertices is n=∣V(G)∣

Since the sets cover all vertices,

n=∣V1∪V2∪⋯∪Vk∣

Because they are disjoint,

 𝑘
𝑛 = ∑ 𝑣𝑖
𝑖=1
| |
Each Vi​is an independent set. But the largest possible independent set in the
graph has size α(G)

So, ∣Vi∣≤α(G) for every i.

Apply inequality
𝑘
| |
∑ 𝑣𝑖 ≤ 𝑘α(𝐺)
𝑖=1

Therefore 𝑛 ≤ 𝑘α(𝐺)
𝑛
𝑘≥ α(𝐺)
but k=χ(𝐺)

𝑛
χ(𝐺) ≥ α(𝐺)

Proof:

Let us prove that theorem by mathematical induction on P.

Initial case: (p=1) G≃ 𝐾1

Clearly, χ(𝐺) = 1 = ∆(𝐺) + 1; ∆(𝐺)=0. Hence the result is true.

Induction hypothesis:

Let us assume that the result is true for any graph on (p-1)-vertices.

Induction step:
Let G be a graph on p-vertrices,p>=2

We claim that the minimum colouring of the graph G is less than or equal to the
max deg of the vertex in the graph G+1.

Let v be a vertex such that deg v=∆(𝐺)

Let 𝑣1, 𝑣2...... 𝑣∆(𝐺)be the vertices adjacent to v.

Consider the graph H=G-v

By induction hypo,χ(𝐺 − 𝑣) ≤ ∆(𝐺 − 𝑣) + 1;

≤ ∆(𝐺) + 1;

(i.e) (G-v) admits ∆(𝐺)+1 coloring.

At least one color say c, which is not in 𝑣1, 𝑣2...... 𝑣∆(𝐺) of G-v

Let us colour the vertex v by c, we get ∆(𝐺) + 1 coloring of G.

Hence the theorem.

Proof:

Let G be a k-chromatic graph which satisfies the hypotheses of the theorem.

Without loss of generality, we may assume that G is K-critical.

We know that if G is k-critical then G is a block.

Also G contains 1-critical,2-critical and 3-critical.

1-critical,2-critical is called complete and 3-critical called odd cycles

Therefore we have k>=4

Case (i): G is 2-connected

If G has a 2-vertex cut (u,v) with k-critical then

𝑑𝑒𝑔 𝑢 + 𝑑𝑒𝑔 𝑣 ≥ 3𝑘 − 5

From well known result δ≤ 𝑑𝑒𝑔 𝑢≤∆ and δ≤ 𝑑𝑒𝑔 𝑣≤∆

Consider max deg and apply above we get

2∆ ≥ 𝑑𝑒𝑔 𝑢 + 𝑑𝑒𝑔 𝑣 ≥ 3𝑘 − 5

2∆ ≥ 𝑑𝑒𝑔 𝑢 + 𝑑𝑒𝑔 𝑣 ≥ 2𝑘 − 1 + 𝑘 − 4

2∆ ≥ 𝑑𝑒𝑔 𝑢 + 𝑑𝑒𝑔 𝑣 ≥ 2𝑘 − 1 ( since 𝑘 ≥ 4 ⇒ 𝑘 − 4 ≥ 0)

2∆ ≥ 2𝑘 − 1

2𝑘 ≤ 2∆ + 1

From this we can say 𝑘(𝐺) ≤ ∆(𝐺)

⇒ χ(𝐺) ≤ ∆(𝐺)

Case (ii): G is 3- connected

Since G is not complete, there are three vertices u,v and w in G such that uv,vw ∈
E and uw ∉ E.

Consider the set of vertices v1,v2,v3….vn

Fix u=v1,w=v2, v=vn and let v3,v4….vn-1 be any ordering.

We can now describe a ∆-coloring(max deg color) of G:

Assign color 1 to v1,v2

Color 2 to v3

Color 3 to v4

Finally since vn is adjacent to two vertices of colour 1 (namely v1 and v2) it is

adjacent to at most (∆-2) other colors and can be assigned one of the colors 2,3,...∆

⇒ χ(𝐺) ≤ ∆(𝐺)

Hence proved.

Proof:
Shadow of Graph:

Proof:
Perfect graph:
A graph G is perfect if χ(H)=ω(H) for every induced subgraph H of G

******************************************************************