Advanced and algorithmic graph theory VO

Exam

The lecture will be assessed by an oral examination. The dates for the oral exams will be specified in agreements with the students.

Advanced and algorithmic graph theory (contents)

1. Connectivity: concepts, parameters and computation
2. Hamiltonicity: necessary conditions, sufficient conditions, special cases
3. Planarity and crossing number: concepts and algorithms
4. Coloring (vertex coloring, edge coloring, list coloring, choosability): concepts and algorithms
5. Perfect graphs (chordal graphs, comparability graphs, intervall graphs)
6. Random graphs: expectations, the probabilistic method, threshold functions
7. Decompositions in graphs (treewidth, pathwidth): concepts and algorithms

1 Connectivity

Graphs and subgraphs

• Definition of a graph G
• Definition of a subgraph H
• Definition of an induced subgraph H
  • If two vertices are included, edges between them must also be
  • Notation: H = G[U] is the subgraph of G induced by U \subset V(G)

Paths, cycles, walks

• Definition of a path P
  • Length: number of edges
• Definition of a cycled (closed path)
• Definition of a walk
  • A path with a repetition of vertices
  • A closed walk is not a cycle

Girth and circumference

• Definition of girth of G, g(G): the length of the shortest cycle of G
  • If cycle-free, g(G) = infinity
• Definition of circumference, circ(G): the length of the longest cycle of G
  • If cycle-free, circ(G) = 0
• Definition of a hamiltonian cycle

Degree

• Definition of the degree of a vertex, deg(v)
  • The number of edges that are incident to the vertex
  • Also: minimal degree delta(G) and maximal degree Delta(G)

Prop 1.1 Every graph G contains a path of length delta(G) and a cycle of length delta(G)+1, provided that delta(G) >= 2.

Remark: There is no clear relationship between the girth g(G) and the minimal degree delta(G).

Distance and diameter

• Definition of the distance d(v,w): the length of the shortest path from v to w
• Definition of the diameter diam(v,w): the maximal distance between v and w
  • G is connected if d(v,w) < infinity for all v, w in V(G)

Prop 1.2 The vertices of a connected graph can always be enumerated if ... (check this)

Connected component

https://en.wikipedia.org/wiki/Component_(graph_theory)

Separation and connectivity

Let A, B in V, A intersection B = Ø, and X subset of V union E

• If every A-B-path contains some element of X, then vi say "X separates A and B".
• "X separates G" if G - X is not connected.
• "X is a separator" if X is a subset of V(G)
• A cut-vertex is a vertex which separates 2 other vertices of the same connected component
• A bridge is an edge which separates its end-vertices.

A graph is k-connected if |G| > k and G-X is connected for all X in V with |X| < k.

The connectivity number kappa(G) is the largest integer k such that G is k-connected.

Definition 9.2: The connectivity number κ(G) is defined as the minimum number of vertices whose removal from G results in a disconnected graph or in the trivial graph (=a single vertex). A graph G is said to be k-connected if κ(G) ≥ k.
from https://win.uantwerpen.be/~vanhoudt/graph/connectivity.pdf

Remark: This also applies to edge-connectivity.

Special cases:

• kappa(G) = 0 -> G is disconnected or G=K_1
• kappa(K_n) = n - 1

If |G| > 1 and G - F is connected for all F in E(G) with |F| < L, we say G is L-edge-connected.

The edge-connectivity number is the largest integer L < Z_F such that G is L-edge-connected. (denoted lambda(G) i think)

Prop 1.3. If |G| > 1 (e.i. non-trivial), then kappa(G) <= lambda(G) <= delta(G).