Types of Graphs
1. Bipartite graph
- A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V.
2. Bivariegated graph
- A bivariegated graph is a graph whose vertex set can be partitioned into two equal parts such that each vertex is adjacent to exactly one vertex from the other set not containing it.
3. Cayley graph
- A Cayley graph is a graph that encodes the abstract structure of a group.
4. Circle graph
- A circle graph is the intersection graph of a set of chords of a circle.
5. Complete graph
- A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.
6. Cubic graph
- A cubic graph is a graph in which all vertices have a degree three.
7. Cycle graph
- A cycle graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3) connected in a closed chain.
8. De Bruijn graph
- An n-dimensional De Bruijn graph of m symbols is a directed graph represnting overlaps between sequences of symbols.
9. Dipole graph
- A dipole graph is a multigraph consisting of two vertices connected with a number of parallel edges.
10. Directed acyclic graph
- A directed acyclic graph is a finite directed graph with no directed cycles.
11. Interval graph
- An interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect.
12. Lollipop graph
- A m,n-lolipop graph is a graph consisting of a complete graph on m vertices and a path graph on n vertices, connected with a bridge.
13. Planar graph
- A planar graph is a graph that can be embedded in the plane in such a way that its edges intersect only at their end points.
14. Split graph
- A split graph is a graph in which the vertices can be partitioned into a clique and an independent set.
15. String graph
- A string graph is an intersection graph of curves in the plane, whereby each curve is called a “string”.
16. Threshold graph
- A threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of either addition of a single isolated vertex to the graph or addition of a single dominating vertex to the graph.
17. Turán graph
- An n,r-Turan graph is a complete multipartite graph formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and connecting two vertices by an edge if and only if they belong to different subsets.
18. Wheel graph
- A wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle.
Graph Coloring
Definition
- Graph coloring is a special case of graph labeling. It is an assignment of labels traditionally called “colors” to elements of a graph subject to certain constraints.
Terminology
i) Vertex coloring
- When referring to graph coloring without any other specifications, it is assumed that the type of coloring is vertex coloring. Vertex coloring is the labeling of the graph’s vertices such that no two vertices share the same edge of the same color.
ii) Chromatic polynomial
- The chromatic polynomial is the number of ways a graph can be colored using a given number of colors. The polynomial equation for a graph G with t colors is : P(G, t) = t(t - 1 )2(t - 2)
iii) Edge coloring
- An edge coloring of a graph is a proper coloring of edges, meaning the assignment of colors to edges so that no vertex is incident to two edges of the same color.
iv) Total coloring
- Total coloring is the type of coloring on both the vertices and the edges of a graph. When used without specification, it is assumed to be proper such that no adjacent vertices, no adjacent edges, and no edge and its end-vertices are assigned the same color.
v) Unlabeled coloring
- An unlabeled coloring of a graph is an orbit of a coloring under the action of the automorphism group of the graph, which is the permutations of coefficients of the coloring.
Applications
i) Scheduling
- Vertex coloring can be used in scheduling problems. In the simplest form, these are problems whereby a set of jobs need to be assigned to time slots, and each job requires one such time slot. Jobs can be scheduled in any order, but pairs of jobs may be in conflict in the sense that they may not be assigned to the same time slot. The chromatic number of the graph is the optimum time to finish all jobs with no conflicts.
- The structure of the graph depend on the details of the scheduling problem. For example, an interval graph is used when assigning aircraft to flights, while a unit disk graph is used to solve bandwidth allocation to radio stations.
ii) Register allocation
- In a computer program, a compiler uses register allocation to improve execution time. Most frequently used values are kept in fast processor registers. These values are then assigned to registers.
iii) Sudoku
- Sudoku is a logic-based, combinatorial number-placement puzzle whereby each row and each column of a 9x9 grid contains the the digits 1 to 9 with no repeats.
- A Sudoku puzzle can be expressed as a graph coloring problem by constructing a 9-coloring of a graph, given a partial 9-coloring
