MM10 Grafteori FALL 2006 (instructor
Bjarne Toft)
MM10 NEWS NO. 10 (November 15, 2006)
The graph on the cover of West's book does not look like the Petersen
graph.
But it is!
The lecture on Wednesday Nov. 15, 2-4 PM, STARTS
AT 2:30 DUE TO THE "Prøv en studiedag". It will
deal with vertex-colourings of graphs, the 4-colour theorem,
and Brooks' Theorem.
The exercises on Monday Nov. 20, 10-12 AM, will deal with
some problems about colouring. Here are formulations in Danish:
- En minimal graf G med kromatisk tal k kaldes k-kritisk. Hvordan
ser de k-kritiske grafer ud for k=1, k=2 og k=3 ?
- Vis at en k-kritisk graf har minimum valens mindst k-1. Vis at en
k-kritisk graf opfylder, at 2 |E(G)| >= (k-1)|V(G)|. For hvilke
k-kritiske grafer er 2 |E(G)| = (k-1)|V(G)| ?
- Vis at en k-kritisk graf (k mindst 3) er
2-sammenhængende.
- Vis at hvis e1 og e2 er to kanter i en k-kritisk graf G (k mindst
3), så er der en (k-1)-kritisk graf, der indeholder e1, men ikke
indeholder e2. Vis at ved fjernelse af højst k-2 kanter fra G er
den resterende graf sammenhængende (dvs en k-kritisk graf er
(k-1)-kant-sammenhængende).
- Vis at omega(G) (størrelsen af en størst mulig
komplet delgraf) er højst det kromatiske tal. Vis at en to-delt
graf har
kromatisk tal = omega. Vis at komplementet af en to-delt graf har
kromatisk
tal = omega.
- Lad G være en multigraf bestående af en ulige kreds
af længde n, hvor kredsens kanter kan være multiple. Vi vil
kalde en
saadan multigraf for en ring-graf. Vis at G's kant-kromatiske tal er
lig med
maximum af de to tal [maximum valensen Delta i G] og [2m/(n-1) rundet
op
til nærmeste hele tal (m er G's kanttal)]. Det kantkromatiske tal er
det mindste antal farver i en farvning af kanterne, hvor to kanter med
et fælles endepunkt altid skal have forskellige farver.
The lecture on Wednesday Nov. 22, 2-4 PM,
will deal with edge-colourings of
graphs.
The lecture on Wednesday Nov. 29, 2-4 PM,
will deal with trees.
The lecture on Wednesday Dec. 6, 2-4 PM,
will deal with Chapter I in the Red Book.
The lecture on Wednesday Dec. 13, 2-4 PM,
will deal with Chapter II in the Red Book.
The lecture on Wednesday Dec. 20, 2-4 PM,
will deal with Chapter III in the Red Book.