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*): - χ′(
*G*) = 1 if and only if *G* is a matching. - χ′(
*G*) ≥ Δ(*G*). - χ′(
*G*) ≤ Δ(*G*) + 1. (Vizing's theorem) - χ′(
*G*) ≤ Δ(*G*) + μ(*G*), where *G* is allowed to be a multigraph. - χ′(
*G*) = Δ(*G*) if *G* is a bipartite graph. (König's bipartite theorem) - χ′(
*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. ...
## References
- 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. |