|
T-colorings
In graph theory, a T-Coloring of a graph G = (V, E), given the set ''T'' of nonnegative integers containing 0, is a function c: V(G) \to \N that maps each vertex to a positive integer (color) such that if ''u'' and ''w'' are adjacent then , c(u) - c(w), \notin T. In simple words, the absolute value of the difference between two colors of adjacent vertices must not belong to fixed set ''T''. The concept was introduced by William K. Hale. If ''T'' = it reduces to common vertex coloring. The ''T''-chromatic number, \chi_(G), is the minimum number of colors that can be used in a ''T''-coloring of ''G''. The ''complementary coloring'' of ''T''-coloring ''c'', denoted \overline is defined for each vertex ''v'' of ''G'' by :\overline(v) = s+1-c(v) where ''s'' is the largest color assigned to a vertex of ''G'' by the ''c'' function. Relation to Chromatic Number :Proposition. \chi_(G)=\chi(G).M. B. Cozzens and F. S. Roberts, T -colorings of graphs and the Channel Assignment Problem. C ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
T-colorings
In graph theory, a T-Coloring of a graph G = (V, E), given the set ''T'' of nonnegative integers containing 0, is a function c: V(G) \to \N that maps each vertex to a positive integer (color) such that if ''u'' and ''w'' are adjacent then , c(u) - c(w), \notin T. In simple words, the absolute value of the difference between two colors of adjacent vertices must not belong to fixed set ''T''. The concept was introduced by William K. Hale. If ''T'' = it reduces to common vertex coloring. The ''T''-chromatic number, \chi_(G), is the minimum number of colors that can be used in a ''T''-coloring of ''G''. The ''complementary coloring'' of ''T''-coloring ''c'', denoted \overline is defined for each vertex ''v'' of ''G'' by :\overline(v) = s+1-c(v) where ''s'' is the largest color assigned to a vertex of ''G'' by the ''c'' function. Relation to Chromatic Number :Proposition. \chi_(G)=\chi(G).M. B. Cozzens and F. S. Roberts, T -colorings of graphs and the Channel Assignment Problem. C ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are connected by '' edges'' (also called ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a set of vertices (also called nodes or points); * E \subseteq \, a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Set (mathematics)
A set is the mathematical model for a collection of different things; a set contains '' elements'' or ''members'', which can be mathematical objects of any kind: numbers, symbols, points in space, lines, other geometrical shapes, variables, or even other sets. The set with no element is the empty set; a set with a single element is a singleton. A set may have a finite number of elements or be an infinite set. Two sets are equal if they have precisely the same elements. Sets are ubiquitous in modern mathematics. Indeed, set theory, more specifically Zermelo–Fraenkel set theory, has been the standard way to provide rigorous foundations for all branches of mathematics since the first half of the 20th century. History The concept of a set emerged in mathematics at the end of the 19th century. The German word for set, ''Menge'', was coined by Bernard Bolzano in his work ''Paradoxes of the Infinite''. Georg Cantor, one of the founders of set theory, gave the following defin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Coloring
In graph theory, 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. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. Vertex coloring is often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as-is. This is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
