User:Darylfoo2000/sandbox


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.

An example of a Bipartite Graph


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.

An example of a Bivariegated graph


3. Cayley graph

- A Cayley graph is a graph that encodes the abstract structure of a group.

An example of a Cayley graph


4. Circle graph

- A circle graph is the intersection graph of a set of chords of a circle.

An example of a Circle graph


5. Complete graph

- A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.

An example of a Complete graph


6. Cubic graph

- A cubic graph is a graph in which all vertices have a degree three.

An example of a Cubic graph


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.

An example of a Cycle graph


8. De Bruijn graph

- An n-dimensional De Bruijn graph of m symbols is a directed graph represnting overlaps between sequences of symbols.

An example of a De Bruijn graph


9. Dipole graph

- A dipole graph is a multigraph consisting of two vertices connected with a number of parallel edges.

An example of a Dipole graph


10. Directed acyclic graph

- A directed acyclic graph is a finite directed graph with no directed cycles.

An example of a Directed acyclic graph


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.

An example of an Interval graph


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.

An example of a Lollipop graph


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.

An example of a Planar graphAn example of a Planar graph


14. Split graph

- A split graph is a graph in which the vertices can be partitioned into a clique and an independent set.

An example of a Split graph


15. String graph

- A string graph is an intersection graph of curves in the plane, whereby each curve is called a “string”.

An example of a String graph


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.

An example of a Threshold 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.

An example of a Turan graph


18. Wheel graph

- A wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle.

An example of a Wheel graph



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.

An example of graph coloring



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.

An example of vertex coloring


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)

A chromatic polynomial


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.

An example of edge coloring


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.

An example of total coloring


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.

An example of an interval graph
An example of a unit disk graph


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

An example of a 9x9 Sudoku grid