CHAPTER 5: Colourings Flashcards
Started with 4 colour theorem:
Any map can be coloured with four colours so that adjacent countries have different colours. I Posed by Guthrie 1852 I Proved by Appel and Haken 1976
DEF:
The chromatic number
The chromatic number χ(G) of a graph G is the least number of
colours needed to colour the vertices so that adjacent vertices have different colours.
Theorem (The four colour theorem)
A planar graph G has χ(G) ≤ 4.
First examples of chromatic number
The complete graph Kn
The complete graph has χ(Kn) = n
First examples of chromatic number
Bipartite graphs
A graph G has χ(G) = 2 if and only if G is bipartite.
First examples of chromatic number
The wheel graph Wn
χ(Wn) = (
3 n even
4 n odd
n+1 vertices:
W_3 : χ =4 since its K_4
W_4: χ=3
ANY COLOURING OF W_n is a colouring of C_n as the wheel and central vertec has to be a new colour since it touches all
First examples of chromatic number
The empty graph En
The only graphs with χ(G) = 1 are the empty graphs En.
How to find χ(G):
in an exam we will find this:
colour with this many colours and explain why we cant do less
Start by finding rough upper and lower bounds.
Upper bound: colour it
Lower bound: often case by case
Finding the χ(G) is NP-hard
So no beautiful answer. But for small graphs not that bad.
How to find χ(G):
Upper bound:
If you can colour the vertices of G with k colours so that adjacent vertices don’t share a vertex, then χ(G) ≤ k.
How to find χ(G): Lower bound:
Lower bound: often case by case
A few trivial tricks:
I If a vertex is adjacent to everything, as in Wn
I If H is a subgraph of G, then χ(G) ≥ χ(H).
χ(C_n):
C2 : χ=2
C_3: χ=3
they all touch each other
C_4:χ=2
C_5: χ=3
If C_n is even then bipartite and 2 colours
3 if n is odd so at least 3
*IN EXAM: last one is the third colour ie try and do with 2 then last with a third
show i cant do with less, explain why.
EXAMPLE GRAPH
7 vertex graph
4 cycles 1243 and 4576
edges 23 and 56 and 17
LOWER BOUND:
- can’t do with one colour
- 2? its not bipartite - there are odd cycles
- we see triangles 123 so need at least 3 colours
tried WLOG: without loss of generality
1red
2blue
3 purple
4 cannot be blue or purple so red
5 and 6 can be blue or purple (one of each)
7 can only be blue or purple as touches 1
so here we cannot colour these in 3 colours so need one more colour
χ(G)≥ 4
upper bound:
colour as 4- then χ(G)=4
(last vertex fourth colour)
EXAMPLE GRAPH
COMPLICATED SEE SLIDES
10 vertices
*we see odd cycles so not bipartite so more than 2
*3: we see triangles but vertex W_5 around D and one around C
also K_4 subgraph DCIH
*At least 4:Attempt
*Considering cases after:
WLOG
By symmetry we can avoid ‘cases’ ie loss of generality
there is a colouring with 4 colours so χ(Q)=4
DEF
∆(G)
∆(G) is the maximum degree of all vertices of G.
Lemma about ∆(G)
χ(G) ≤ ∆(G) + 1
Proof.
Colour the vertices one by one in any order.
Colour vertices 1 by 1. SUppose youve coloured vertices V_1 and V_2 using at most ∆(G) + 1
χ(G) ≤ ∆(G) + 1
Proof.
I think in exam…
Proof.
Colour the vertices one by one in any order.
Colour vertices 1 by 1. SUppose youve coloured vertices V_1 and V_2 using at most ∆(G) + 1 colours and now we want to colour V_(k+1)
Any colour that V_(k+1) is adjacent to cant be used.
All we know is that the edges out of V_(k+1) is at most ∆(G). Some might not already be coloured, some may have same colours. We have ∆(G) + 1 colours to use. The worst case is that we have used ∆(G) colours so we can colour this anyway by the last unused colour.
EXAMPLE: The bound is tight, but for very few graphs:
χ(G) ≤ ∆(G) + 1
**
χ(Kn) = n = ∆(Kn) + 1
For n odd, χ(Cn) = 3 = ∆(Cn) + 1
Theorem (Brooks)
If G isn’t a complete graph or an odd cycle, then χ(G) ≤ ∆(G).
Suppose you have some things you want to separate into groups, but certain things can’t be in the same group. How many groups do you need?
- Group vacation, several cottages, some people don’t get on
- Storing chemicals, some react dangerously with each other
Make a graph G with:
- Vertices are the things
- Edges mean the vertices can’t be in the same group
The groups are the colours.
χ(G) is the lowest feasible number of groups
EXAMPLE: X indicated two people cant be in the same groups
AB X AC X AF X AG X BC X BD X BG X CD X CE X DE X DF X FE X EG X FG X
Circulate graph* So this forms a graph with 7 vertices and drawing these edges graph coloured WLOG A=1 B=2 G=3 try to colour in 3 colours as odd cycles indicate not bipartite C cannot be 1 or 2 c=3 D=1 as connected to C and B F=2 adjacent to G,A and D last vertex E is adjacent to all 3 colours so must be 4 colours
SO minimum number of groups are 4
Theorem
Chromatic Number for planar graphs
For G a planar graph χ(G) ≤ 6.
For G a planar graph χ(G) ≤ 6
PROOF
Step 1: Using Euler’s Theorem
Definition
δ(G) denotes the minimum degree of all vertices in G.
Lemma
For G a simple planar graph δ(G) ≤ 5
Step 2: Induction
We proved χ(G) ≤ ∆(G) + 1 by colouring the vertices of G in any order. The Lemma bounds δ(G) and not ∆(G); need to be a little smarter.
Lemma
For G a simple planar graph δ(G) ≤ 5
PROOF
Assume not, then δ(G) bigger than 5
so d(v) ≥ δ(G) ≥ 6
So combine this with V-E handshaking:
2E = sum of d(v) ≥ 6V
- Euler’s Theorem V − E + F = 2
- Face-Edge handshaking
V≤2E/6= EF/3 ≤ 2E/3
Bounds on d(F) come from simple so no loops and multiple edges so d(F) bigger than or equal to 3
*Simple, so d(f ) ≥ 3 for all faces. So 2E ≥ 3F
Proof of the Six Colour Theorem
Assume G is planar. We can assume that G is simple.
Induct on n the number of vertices
Base case: n ≤ 6
At most six vertices, so can give each vertex a different colour.
Inductive Step
Assume that G has n vertices, and every planar simple graph with less than n vertices can be coloured with six colours.
I By the Lemma, G has a vertex v with d(v) ≤ 5
I The graph G \ v has n − 1 vertices, so can be six coloured
I Now colour v
DEF Chromatic index
χ’(G)
The chromatic index χ’(G) denotes the minimum number of colours needed to colour the edges of G so that any two edges that share a vertex have different colours.
Suppose six teams A − F are in a soccer league, and each team will play three games: A X B X X C X D X X E X X X F If each team plays one game a week, can the tournament be run in three weeks? How about if we want AB and DE to play on different weeks?
Make it a graph: Colour minimum colours EDGES
In the application: the colours were the weeks?
Every team playing at least 3, so we look to see if 3 is minimum
6 teams and edges are games they must play
triangle ABC DEF
4 cycles ABED
CBEF
label numbers
for each vertex they dont see the same number twice coming out of them: teams play one game per week at max
WLOG
AB=2
AC=3
CB=1
then we must have AD=1 CF=2 BE =3 ED=2 EF=1 DF=3
in exam
We will definitely do proofs similar to 6 colour, ie eulers theorem, handshaking, simple proofs
colouring vertices, chromatic number prove and colour by cases that cant be done with less
we will also look at chromatic index and….
lower bound try- try to make no choices and use every case! SHOW if choice made- try with more colours again SHOW then done
- quote Vizings theorem
- define chromatic index of this graph
- justify
χ’(K4) =
χ’(K4) = 3
K_4 has vertices of degree 3 so χ’(K4) is at least 3. Trying to colour works:
Lemma on and degrees
χ’ (G)
Lemma
χ’ (G) ≥ ∆(G)
χ’(K5) =
χ’(K5) = 5
We know its at least 4 as degrees are all 4: attempting this leads us to need 5
symmetry was used
so we need to use every case unless cant use symmetry*****]
another proof: that bigger than or equal to 5
K5 has 10 edges. In any graph, if we have k edges of one colour all 2K vertices they touch have to be different. In K5 at most 5 / 2 = 2 edges of any one colour. If I have 4 colours can do at most 4 x 2 = 8 edges. Not enough
Theorem (Vizing)
χ’(
ON EXAM
For a simple graph χ’(G) = ∆ or ∆ + 1
SO TRY ∆ then we know ∆ +1 for EDGES coloured
**in EXAM??
TRY delta if not
we know delta +1
One method to find χ’(G) with proof:
We know χ’(G) ≥ ∆(G). Try to colour it with ∆(G)
- If we can, we have shown χ’(G) = ∆
- If we can’t, prove it: so we know χ’(G) ≥ ∆ + 1
- Find a colouring with ∆ + 1 colours
Example
Kn for n odd
Kn for n odd Suppose n = 2k + 1 is odd.
- Then ∆(Kn) = n − 1 = 2k
- Kn has k(2k + 1) edges.
- We can have at most k edges of any given colour
*So using 2k colours, can only colour 2k
2 < k(2k + 1) edges
EXAMPLE: NOTE
In lemma we need to use G is simple or we could just add loops or null edges eg wheel
Example: K_5
Kn for n odd
????
we have 5 vertices, 10 edges we have at least two different colours.
K vertices of one colour then all 2k edges that touch must have different colour to each other
10 edges so need 5 colours
Example
Kn for n odd
…
If n is odd we know χ’(G) ≥n
∆((K_n) = n-1
By counting arguement, K_n has nC2 = n(n-1)/2 edges. If n odd , n=2k+1.
#edges (2k+!)(2k)/2 = k(2k+1) How many edges can i have of one colour? Half the # vertices 2k+1 /2 = k + 0.5 ***
So if we have n-1 =2k colours we can only colour (#colours) #edges of every colour 2k(k) less than 2k^2 +k
=total # edges
Chromatic Polynomial
DEF
counting different colours that are possible
*not unique to graphs
Let G be a SIMPLE graph, and let k ≥ 1 be an integer. The
chromatic polynomial P_G (k) is the number of different ways to
colour the vertices of G with k colours, so that adjacent vertices have different colours.
PG (k) = 0
PG (k) = 0 ⇐⇒ 0 ≤ k < χ(G)
Chromatic Polynomial
FINDING
In easy examples, can colour vertex by vertex:
can be written χ_G(k)
- P_{E_n}(k) =k^n
- P{Kn}(k) = k(k − 1)(k − 2)· · ·(k − n + 1)
- If T is a tree with n vertices, then PT (k) = k(k − 1)n
Chromatic Polynomial
of E_n
empty graph on n vertices
For 3 colours we have 3 choices for every vertex as none are adjacent
P_{E_5}(3)=3^5
P_{E_n}(k)=k^n
for k colours
Chromatic Polynomial
of K_n
For complete graph every single vertex is adjacent to every other.
For k colours:
I choose K colours for the first
for second vertex v_2 cant use the same colour as v_1 so k-1
* V_3 cant be the same colour as 1 or 2 so k-2 choices
For K_4 we need at least 4 colours
- P{Kn}(k) = k(k − 1)(k − 2)· · ·(k − n + 1)
EXAMPLES
chromatic # of tree
x
x-x-x<
x
ABCD
st E is connected to C
order might affect Starting in middle at vertex B we have K colours A has k-1 as cant be the same as B C has k-1 as cant be the same as A D has k-1 as cant be the same as c E has k-1 for the same reason
PG (k) = K(K-1)^{}?
CHROMATIC polynomial of a TREE
For any tree:
ALL TREES ON n VERTICES have the SAME CHROMATIC POLYNOMIAL
only adjacent to one thing if it was adjacent to two things there would be a loop and we wouldn’t have a tree because it’s only adjacent to one thing . We can only choose from k - 1 colours for every other vertex after our first.
For tree T on n vertices
P_T (k) = k(k-1)^{n-1}????
not?
* If T is a tree with n vertices, then PT (k) = k(k − 1)n????
EXAMPLE
CHROMATIC polynomial of
A-B-D-C-A and edge B-C
- choose colour A out of K
- B has k-1 choices
- If we choose D next we see K-1 ways as its adjacent to B
*But then colouring C gives a problem:
We might have A and D the same colour (they werent adjacent to each other but are to C)
If theyre the same then C is only touching two colours: k-2 choices
If theyre different then C is touching 3 so k-3
*If we start from a different way we can find in another order by looking at the triangle first otherwise we have to do case by case analysis
P_G (k) = k(k-1)(k-2)^2
why not?
P_G (k) = k(k-1)(k-2)(k-3)?
WHICH??
EXAMPLE
Bowtie graph
CHROMATIC polynomial of
A-C-D-E-C-B-A
A-k B-k-1 C-k-2 D-k-1 E-K-2
P_G (k) = k(k-1)^2(k-2)^2
CHROMATIC polynomial of
U-V-W
V-X-Y-W
W-X
Y-Z
Z-K Y-k-1 X-k-1 W- k-3 (adjacent to 2 already coloured that are different colours) V-k-2 u-k-2`
P_G (k) = k(k-1)^2(k-2)^2(k-3)
CHROMATIC polynomial
PATTERNS
deg(K_n)= #vertices
colour vertices with i choices
to the powers total n
CASE BY CASE EXAMPLE
CHROMATIC polynomial
C_4
the chromatic number is hard as cases are involved:
k ways to colour vertex 1
I k − 1 ways to colour vertex 2
I k − 1 ways to colour vertex 3
Don’t know if v1 and v3 have same colour
__________
CASE 1: 1 and 3 same colour
1 has k choices 2 has k-1 choices
3 is the same as 1 so no choice
4 has k-1 choices as adjacent to 1 and 3
k(k-1)^2
(powers =3 not 4)
CASE 2: 1 and 3 different colours
1 has k choices
3 is only adjacent to 2 and is not the same as 1 in our case so has k-1 choices (forced different colour)
2 we have forced 1 and 3 to be different so k-2 choices
4 we know 1 and 3 different colours so k-2
k(k-1)(k-2)^2
Factorising:
k(k-1)(k-1)
k(k-1)(k^2-4k+4)
ADDING THESE
P_C(k)= k(k-1)[k^2-3k+3]
same colour in chromatic poolynomial
IF THEYRE THE SAME COLOUR WE CAN MERGE VETICES
(2)-(1,3)-(4)
(1,3) has k
(2) has k-1
(4) has k-1
(2)=(1,3)=(4)
CASE BY CASE
CHROMATIC polynomial
Case 1: v1 and v2 are the same colour
If they’re the same colour, then we can make them same vertex…
Case 2: V2 and v3 are different colours
If there’s an edge between two vertices, then they need to be different colours.
Different colour case chromatic polynomial
BY SAYING theyre the different colours we have added/forced an edge 1-3 when there wasnt one
1-2-3-4 and added 1-3 by saying 1 and 3 different colours
WHEN DO WE CONSIDER CASES chromatic polynomial
for any graphs with vertices (pairs) which aren’t adjacent, we consider the cases of whether or not they have different colour
CHROMATIC polynomial of C_5
We consider cases for non adjacent vertices:
1=k
5 and 2 could be the same
CASE 1: 5 and 2 same 1=k 5=k-1 2=1 choice 3=k-1 4=k-2 as adjacent to 5 and 3
k(k-1)^2(k-2)
CASE 2: 5 and 2 different** 1=k 2=k-1 5=k-2 3=now 4 and 2 could be the same so we have another case **4 and 2 the same 4=1 3=k-1 as only adj to one colour
k(k-1)^2(k-2)
CASE 3:5 and 2 different and 4 different to 2 (4 adj to 5 so will be diff)
1=k
2=k-1
5=k-2
4=k-2 as adjacent to 5 and is not the same as 2
3=k-2 as adjacent to 2 different colours
k(k-1)(k-2)^3
so polynomial is 2k(k-1)^2(k-2) + k(k-1)(k-2)^3 =k(k-1)(k-2)[2(k-1) +(k-2)^2] =k(k-1)(k-2)[2k-2+k^2+4-4k] =k(k-1)(k-2)[k^2-2k+2]
CHROMATIC polynomial of C_5
notes
in the lecture he consider different cases to example:
CASE 1 1, 3 ,4 diff colours
k(k-1)(k-2)^3
= my case 3 symmetry
CASE 2 1 and 3 same colour
= my case ??
CASE 3 1 and 4 same colour
Example
G_{+XY}
adding Vertex XY to original
P_{G_{+XY}}(k) = # colourings in P_G(k) where X and Y have different colours
G_{X=Y}
creating new Vertex by merging X and Y
multiple edge merged (X=Y)
P_{G_{+XY}} = # colouringd og G where X and Y have same colour
LEMMA
Suppose that G is a graph, and x and y are two vertices that
aren’t adjacent. Define:
CHROMATIC POLYNOMIAL
I G+xy to be the graph with the edge xy added
I Gx=y to be the graph with x and y identified
Then:
PG (k) = PG+xy(k) + PGx=y(k)
LEMMA
Suppose that G is a graph, and x and y are two vertices that
aren’t adjacent. Define:
PG (k) = PG+xy(k) + PGx=y(k)
Proof.
Consider a colouring of G; in some of them x and y will have
different colourings, and in others x and y will have the same colour. The colourings in the first case are exactly the colourings of G+xy , the colourings in the second are the colourings of Gx=y.
The chromatic polynomial of C5
notes???
during the 3 which become two cases
joining vertices 1 and 4
adding edge between 1 and 4
The chromatic polynomial of C5
Three cases, but two are the same: I Case 1: 1,3 and 4 all have different colours I Case 2: 1 and 3 have the same colour I Case 3: 1 and 4 have the same colour By symmetry, Cases 2 and 3 are the same. I Case 1 gives: k(k − 1)(k − 2)^3 I Cases 2 and 3 each give: k(k − 1)^2(k − 2)
PC5(k) = k(k − 1)(k − 2)3 + 2k(k − 1)2(k − 2)
= k(k − 1)(k − 2)[k^2 − 4k + 4 + 2k − 2]
= k(k − 1)(k − 2)(k^2 − 2k + 2)
Chromatic number
Chromatic index
Chromatic polynomial
Chromatic number χ(G): colour vertices with fewest colours
I Chromatic index χ’(G): colour edges with fewest colours
I Chromatic polynomial P_G (k): number of ways to colour
vertices with k colours
- Some graphs: colour vertex by vertex: if just triangles then do vertex by vertex
- in general case by case
Chromatic polynomial of C4 and a Lemma
Let x and y be two non-adjacent vertices in G. Then
PG (k) = PG+xy
(k) + PGx=y (k)
so CASE 1 and 3 different graphs
k(k − 1)(k − 2)^2
1-2-3-4-1 and 1-3
CASE 1 and 3 same colour
2=(1,3)=4
k(k − 1)^2
PC4
(k) = k(k − 1)(k − 2)2 + k(k − 1)2 = k(k − 1)(k^2 − 3k + 3)
Lemma (Deletion-Contraction)
Let H be a graph, and let e be an edge in H. Then
PH(k) = P_{H\e}(k) − P{H/e}(k)
The edge e is between xy
H = G + xy,
H \ e = G,
H/e = Gx=y
** P_H(k)
= deleted edge P - contracted edge P
from PG (k) = PG+xy(k) + PGx=y (k)
PG (k) - PGx=y (k) =
PG+xy(k)
- we use this to get a smaller graph
- one will always have a smallr degree
Chromatic polynomial is a polynomial
Theorem
Let G be a simple graph. Then PG (k) is a polynomial in k.
Moreover, if G has n vertices and m edges, then
PG (k) = k^n − mk^{n−1} + lower order terms
Chromatic polynomial is a polynomial
PROOF
Proof idea:
Induct on the number of edges using deletion-contraction.
Base case: m = 0
If G has no edges and n vertices, then G = En empty graph.
PEn = k^n is a polynomial of the right form.
Inductive step
Assume that G has m > 0 edges and n vertices, and that for any
graph H with l < m edges and p vertices, we have
PH(k) = k^p − lk^{p−1} + · · · .
Let e ∈ G be any edge:
- G \ e has n vertices and m − 1 edges
- G/e has n − 1 vertices and at most m − 1 edges
So by the inductive hypothesis, theorem holds for G \ e and G/e
So applying Deletion-Contraction:
PG (k) = PG\e
(k) − PG/e(k)
= (k^n − (m − 1)k^{n−1} + · · ·) −
(k^{n−1} − · · · )
= k^n − mk^{n−1} + · · ·
Which is what we needed to show
Compute c_4 chromatic polynomial using deletion contraction
P_(c_4)(k)= P_(C4\e) (k) - P_(C4/e)(k)
ie deleted - contracted
P_(C4\e) (k) = is a tree so chromatic polynomial k(k-1)^3
P_(C4/e)(k) =contracted to triangle so k(k-1)(k-2)
SO deletion contraction gives
P_(c_4)(k)= k(k-1)[k^2 -3k+3]
Deletion-Contraction as an algorithm
I Can always find PG (x) by iterating deletion-contraction
I In practise, often faster to add edges
(we are taking them away in deletion contraction and easier to calculate chromatic polynomial)
how can we make into tree or how can we make into triangle
= determines which way we use to find
Information in PG (k)
ON EXAM
chromatic polynomial: is not unique to graphs but we CAN find out some info about the graph from it
(same polynomial for all trees for example, K_n, E_n)
I Number of vertices is the degree
I Number of edges is negative the coefficient of next highest term
neg coeff of 2nd highest term
I χ(G) is the lowest k with PG (k) not equal to 0.
____
EXAM QUESTION:
SUppose you know the graph has this chromatic polynomial. How many vertices? How many edges?
If i plug in K it will tell me how many ways can i colour the vertices in K colours.
The chromatic number is the lowest amount of colours so lowest term not less than or equal to 0
*C_4 i cant plug 0 or 1 but i can plug in 2
might have to solve one in exam
*C_5 chromatic number is 3 so we know that the polynomial will have (k-1) and (k-2) as factors and a quadratic part left (degree must be 5, 5 edges so -5 is coeff of second highest k^4 term has coeff -5)
= k(k − 1)(k − 2)(k^2 − 2k + 2)
Use induction to calculate PG (k) for a family of graphs. We’ll
do Cn
Use induction to calculate PG (k) for a family of graphs. We’ll
do Cn
Gluing formulas for graphs that are nearly disconnected
deletion contraction on graph
a-b-c-d-a and edge e between a and c
G/e is graph where edge e contracted
b) = (a,c)=(d
(b) -(a,c)-(d)
* labels just to write this in notes, unlabelled examples
PROOF THAT SHOWS UP ON THE EXAM SOMEHOW??
Theorem
Let G be a simple graph. Then PG (k) is a polynomial in k.
Moreover, if G has n vertices and m edges, then
P_G (k) = k^n − mk^{n−1} + lower order terms
Proof idea:
Induct on the number of edges using deletion-contraction.
Base case: m = 0
If G has no edges and n vertices, then G = En empty graph. PEn = k^ n
is a polynomial of the right form
Inductive step
Assume that G has m > 0 edges and n vertices, and that for any graph H with l < m edges and p vertices, we have
PH(k) = k^p − lk^{p−1} + · · · .
Let e ∈ G be any edge:
- G \ e has n vertices and m − 1 edges
- G/e has n − 1 vertices and at most m − 1 edges
So by the inductive hypothesis, theorem holds for G \ e and G/e
So applying Deletion-Contraction:
PG (k) = PG\e
(k) − PG/e(k)
= (k^n − (m − 1)k^{n−1} + · · ·) −
(k^{n−1} − · · · )
= k^n − mk^{n−1} + · · ·
what we needed.
Deletion contration for graph
abcdga and bfc
METHOD 1
so P_G(k)
edge e is ga
P_G
=P_G\e(k) - P_(G/e)(k)
PG\e(k) =
(k-1)P_C(k)
4 cycle and one edge going off
P_(G/e)(k)=
k(k-1)(k-2)^2
4 cycle and an edge between 2 non adjacent
looks like ice-cream cone
(edge between them)
(k-1) - k(k-1)(k-2)^2
=k(k-1)(k^3-5k^2+10k-7)
5 vertices = 5 degrees
can be cplpured in 2 colours- bipartite
chromatic poly of bipartite
is bipartite so doesnt have a k-2 term!
potentially in exam:
state deletion contraction, prove deletion contraction,
use deletion contraction to prove its a polynomial
YOU WILL HAVE TO PROVE EULERS THEOREM!!
Calculating the chromatic polynomial of Cn
Let e be any edge of C_n. Then:
C_n /e ∼= C_{n-1}
C_n\e = P_n a tree so P_{P_n}(k)=k(k-1)^{n-1}
(*if we delete edge e its k(k-1)^{n-1}
*if we contract edge e then it becomes C_{n-1}, looks like we can find C_n by ….C_0}
SO we should be able to find P_{C_n }(k) using induction:
P4(k) =k^4 − 4k^3 + 6k^2 − 3k
P5(k) =k^5 − 5k^4 + 10k^3 − 10k^2 + 4k
P6(k) =k^6 − 6k^5 + 15k^4 − 20k^3 + 15k^3 − 5k
P7(k) =k^7 − 7k^6 + 21k^5 − 35k^4 + 35k^3 − 21k^2 + 6k
Looks like:
Pn(k) = (k − 1)^n + (−1)^n(k − 1)
(pascals triangle)
COMPUTING FAMILY OF GRAPHS CHROMATIC POLYNOMIAL
probably in exam?
using induction contraction (similar to proving its a polynomial)
- there was an old exam where they used a different way to find chromatic polynomial for C_n but for the Cn-cycle this way
- ON THE EXAM: There are questions where you use induction to find the chromatic formula; deletion contraction allows for this
- we know for trees, we know for complete, we know for empty in this way
- on exam one that could show up is glue vertex / glue edge
Prove that:
Looks like:
P_{C_n}(k) = (k − 1)^n + (−1)^n(k − 1)
(we will have to so something similar in exam)
USE INDUCTION:
BASE CASE: n=3 (the first time C_n is a simple graph)
P_{C_3}(k) = k(k-1)(k-2)= k^3 -3k^2 +2k
as required
INDUCTIVE STEP: Assume that we know P_{C_{n-1}}(k) = (k-1)^{n-1} +(-1)^{n-1}(k-1)
want to find P_{C_n}(k), if e is any edge then C_n\e = P_n
o-o-o-o..-o-o n vertices
SO
P_{C_n\e}(k) = k(k-1)^{n-1}
And by C_n\e =C_{n-1}
inductive hypothesis implies
P_{C_n/e}= (k-1)^{n-1} + (-1)^{n-1}(k-1)
SO by deletion contraction:
P_{C_n}(k)
=k(k-1)^{n-1} - [ (k-1)^{n-1} + (-1)^{n-1}(k-1)]
=(k-1)^{n-1}[k-1] +(-1)^n(k-1)
WHICH IS WHAT WE NEEDED TO SHOW
EXAMPLE
G is 2 disjoint triangles
Dont affect each other so we can have combinations between them also:
P_G(k) = P_(C_3)(k)* P_(C_3)(k)
1=k
2=k-1
3=k-2
so k^2(k-1)^2(k-2)^2
Lemma
DISJOINT UNIONS CHROMATIC POLY
If G is the disjoint union of G1 and G2, then
P_G (k) = PG_1(k)PG_2(k)
Proof.
Colouring G is exactly the same as colouring G1 and G2
independently.
NOTES
Lemma
DISJOINT UNIONS CHROMATIC POLY
SINCE P_G(0) =0 by definition . P_G(k) is always divisible by K. (its always a factor) By our lemma on disjoint unions if G has connected components then P_G(k) is divisible by K^C.
2 components then divisible by k^2
Gluing formulas: when G isn’t quite a disjoint union
Idea: Colour G1, then extend to a colouring of G2.
LEMMA
gluing two graphs along a vertex
Lemma
If G is made by gluing G1 and G2 along a vertex v, then:
PG (k) = (1/k)PG_1(k)PG_2(k)
LEMMA WE WONT USE
G has C connected components
IFF K^C is the highest power of K dividing P_G(K)
LEMMA gluing two graphs along a vertex Lemma If G is made by gluing G1 and G2 along a vertex v, then: PG (k) = (1/k)PG_1(k)PG_2(k)
PROOF
Proof.
First colour G1 in any of the PG1 (k) ways. Now, vertex v of G2 is already coloured, but none of the rest. Since the colours are interchangable, exactly 1/k of the ways of colouring G2 will have
the right colour at v
consider possible colour combinations of the two triangles, we can only glue them together if the colours are the same for the glued vertex
Lemma
If G is made by gluing G1 and G2 along an edge e, then
Lemma
If G is made by gluing G1 and G2 along an edge e, then
PG (k) = 1/{k(k − 1)} P_{G_1}(k)P_{G_2}(k)
(probability/proportion that glue together)
EXAMPLE 2 triangles glued at a vertex:
BOWTIE
P_G(k)= k(k-1)^2(k-2)^2
= [P_C_3(k)^2]/k
consider possible colour combinations of the two triangles, we can only glue them together if the colours are the same for the glued vertex
EXAMPLE 2 triangles glued at an edge
a-b-c-d-a and b-d
P_G(k) = k(k-1)(k-2)^2
=[P_(c_3)(k)^2]/[k(k-1)]
graph
abcda and bfd
METHOD 2
we saw that we could find the polynomial by using deletion contraction twice.
it is easier to add an extra Edge use case by case looking at non-adjacent vertices:
CASE 1: v and w have same colour: k choices and k-1 choices for each of other 3 k(k-1)^3
CASE 2: v and w have different colours: K choices for v, k-1 choices for w and k-2 choices for others k(k-1)(k-2)^3
P_G(k) = k(k-1)^3 + k(k-1)(k-2)^3
=k(k-1)[k^3-5k^2 +10k-7]
Gluing:
in exam
only edge or vertex would come up
cant do complete graphs but gluing more complicated wont come up
*given a graph to glue
*could ask to prove or state or use specific method gluing formula probably not but more likely deletion contraction
*Here is a graph what is the chromatic polynomial:
we could use deletion contraction loads of times so in exam only a few times used
case by case or deletion contraction (in only a few cases)
*could do by deletion contraction but look if case by case?
*POINTING OUT:
graph
**in exam?
graph abcd and edge e connected to every vertex
obervation
:
K choices for the central Vertex so can never use that colour again
so P_g(k) =kP_(C_4)(k-1) works whenever you have one Vertex to everything
