FACTOID # 30: If Alaska were its own country, it would be the 26th largest in total area, slightly larger than Iran.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Edge coloring

In graph theory, as with its vertex counterpart, an edge coloring of a graph, when mentioned without any qualification, is always assumed to be a proper coloring of the edges, meaning no two adjacent edges are assigned the same color. Here, "adjacent" means sharing a common vertex. A proper edge coloring with k colors is called a (proper) k-edge-coloring and is equivalent to the problem of partitioning the edge set into k matchings. A graph that can be assigned a (proper) k-edge-coloring is k-edge-colorable. A 3-edge-coloring of a cubic graph is sometimes called a Tait coloring. A diagram of a graph with 6 vertices and 7 edges. ... A 3-coloring suits this graph, but fewer colors would result in adjacent vertices of the same color. ... One major problem that has plagued graph theory since its inception is the lack of consistency in terminology. ... This article is about mathematical matchings. ... In the mathematical field of graph theory, a cubic graph is a graph where all vertices have degree 3. ...

The smallest number of colors needed in a (proper) edge coloring of a graph G is the chromatic index, or edge chromatic number, χ′(G), also sometimes notated χ1(G). A graph is k-edge-chromatic if its chromatic index is exactly k.

Some properties of χ′(G):

1. χ′(G) = 1 if and only if G is a matching.
2. χ′(G) ≥ Δ(G).
3. χ′(G) ≤ Δ(G) + 1. (Vizing's theorem)
4. χ′(G) ≤ Δ(G) + μ(G), where G is allowed to be a multigraph.
5. χ′(G) = Δ(G) if G is a bipartite graph. (König's bipartite theorem)
6. χ′(G) = Δ(G) if G is simple, planar and Δ(G) ≥ 8. (Vizing 1965)

Here Δ(G) is the maximum degree; and μ(G), the multiplicity. This article is about mathematical matchings. ... One major problem that has plagued graph theory since its inception is the lack of consistency in terminology. ... In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjoint sets with two vertices of the same set never sharing an edge. ... One major problem that has plagued graph theory since its inception is the lack of consistency in terminology. ... One major problem that has plagued graph theory since its inception is the lack of consistency in terminology. ...

As we can see from above, χ′(G) equals either Δ(G) or Δ(G) + 1. When χ′(G) = Δ(G), G is said to be Class 1; otherwise, Class 2. Holyer (1981) proved that it is NP-complete to determine whether a simple graph is Class 1 or Class 2. Some efforts have been made to give a partial characterization. For example, Vizing (1965) determined a simple, planar graph is Class 1 if its maximum degree is at least 8. When the maximum degree is at most 5, it is known that some simple, planar graphs are Class 2. The remaining cases are still unsolved and can be summarized as follows: In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... One major problem that has plagued graph theory since its inception is the lack of consistency in terminology. ...

Vizing's planar graph conjecture. (Vizing 1965)

All simple, planar graphs with maximum degree 6 or 7 are Class 1.

This conjecture has implications for the total coloring conjecture. In graph theory, total coloring is a type of coloring on the vertices and edges of a graph. ...

• Holyer, Ian (1981). The NP-completeness of edge-coloring. SIAM J. Comput. 10, 718–720.
• Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
• König, D. (1916). Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Mathematische Annalen 77, 453–465.
• Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph. Diskret. Analiz. 3, 25–30.
• Vizing, V. G. (1965). Critical graphs with given chromatic class (in Russian). Metody Diskret. Analiz. 5, 9–17.

Results from FactBites:

 MINIMUM EDGE COLORING (91 words) A coloring of E, i.e., a partition of E into disjoint sets Cardinality of the coloring, i.e., the number of disjoint sets The maximization variation in which the input is extended with a positive integer k, and the problem is to find the maximum number of consistent vertices over all edge-colorings with k colors, is approximable within e/(e-1) [
More results at FactBites »

Share your thoughts, questions and commentary here