Term
|
Definition
| an assignment of colors to the vertices so that adjacent vertices have distinct colors |
|
|
Term
|
Definition
| a vertex coloring using k colors |
|
|
Term
|
Definition
| a graph that permits a k-coloring |
|
|
Term
|
Definition
| the min number of colors needed for any proper k-coloring |
|
|
Term
|
Definition
| the removal of any vertex of G reduces the chromatic number |
|
|
Term
| Independent Set of Vertices |
|
Definition
| a subset of G where no pair of vertices are adjacent |
|
|
Term
|
Definition
| the max size of an independent set |
|
|
Term
|
Definition
| the length of the smallest cycle |
|
|
Term
|
Definition
| a G where there is only one way to color the G with k colors where no two vertices have the same color. |
|
|
Term
|
Definition
| an assignment of colors to the edges of G |
|
|
Term
|
Definition
| a G where incident egdes receive distinct colors |
|
|
Term
|
Definition
| X1(G), the min number of colors required in a proper edge coloring of G |
|
|
Term
|
Definition
| a graph that represents the adjacencies between edges of G |
|
|
Term
|
Definition
| a subgraph of G that is a complete graph |
|
|
Term
|
Definition
| a graph drawn in the plane with no crossing edges |
|
|
Term
|
Definition
| a graph that is a planar graph |
|
|
Term
|
Definition
| the lowest number of edge crossings of a planar drawing of G |
|
|
Term
|
Definition
|
|
Term
|
Definition
| the unbounded region outside the graph |
|
|
Term
|
Definition
| number of edges surrounding a face |
|
|
Term
|
Definition
|
|
Term
|
Definition
| adding any vertex of degree 2 on an edge of G |
|
|
Term
|
Definition
| a graph where no addition edges can be added to G while keeping the graph planar |
|
|
Term
|
Definition
| a graph which has a vertex for each face region of G, and an edge for each edge in G joining two neighboring faces |
|
|
Term
|
Definition
| delta(G)<=X1(G)<=delta(G)+1 |
|
|
Term
|
Definition
If G is a bipartite graph, then
X1(G) = delta(G) |
|
|
Term
|
Definition
| n vertices minus q edges plus f faces equals two |
|
|
Term
| Kuratowski's Characterization of Planar Graphs |
|
Definition
| G is planar iff it contains no subgraph that is a subdivision of K(5) or K(3,3) |
|
|
Term
|
Definition
| max degree of a vertex in G |
|
|
Term
|
Definition
| Most Beautiful Women in the Universe |
|
|
