Shared Flashcard Set

Details

Graph Theory Final
GTF
30
Mathematics
Undergraduate 4
12/11/2010

Additional Mathematics Flashcards

 


 

Cards

Term
Vertex Coloring
Definition
an assignment of colors to the vertices so that adjacent vertices have distinct colors
Term
k-coloring
Definition
a vertex coloring using k colors
Term
k-colorable
Definition
a graph that permits a k-coloring
Term
Chromatic Number
Definition
the min number of colors needed for any proper k-coloring
Term
k-critical
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
Independence Number
Definition
the max size of an independent set
Term
Girth
Definition
the length of the smallest cycle
Term
Uniquely k-colorable
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
Edge Coloring
Definition
an assignment of colors to the edges of G
Term
Proper Edge Coloring
Definition
a G where incident egdes receive distinct colors
Term
Edge-chromatic Number
Definition
X1(G), the min number of colors required in a proper edge coloring of G
Term
Line Graph
Definition
a graph that represents the adjacencies between edges of G
Term
Clique
Definition
a subgraph of G that is a complete graph
Term
Planar Graph
Definition
a graph drawn in the plane with no crossing edges
Term
Plane Graph
Definition
a graph that is a planar graph
Term
Crossing Number
Definition
the lowest number of edge crossings of a planar drawing of G
Term
Face in a Plane Graph
Definition
the divided regions
Term
Outer Face
Definition
the unbounded region outside the graph
Term
Length of a Face
Definition
number of edges surrounding a face
Term
Triangulation
Definition
maximal planar graphs
Term
Subdivision
Definition
adding any vertex of degree 2 on an edge of G
Term
Maximal Planar
Definition
a graph where no addition edges can be added to G while keeping the graph planar
Term
Dual Graph
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
Vizig's Thm
Definition
delta(G)<=X1(G)<=delta(G)+1
Term
Konig's Thm
Definition
If G is a bipartite graph, then
X1(G) = delta(G)
Term
Euler's Formula
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
Delta of G
Definition
max degree of a vertex in G
Term
Bonnie
Definition
Most Beautiful Women in the Universe
Supporting users have an ad free experience!