Edge coloring

子是一種完美匹配，因為其結果括了圖G中原來的所有頂點；此外，若將一個k-正則圖進行1-分解則與將該k-正則圖進行k種顏色的邊著色（英语：Edge coloring）等價。2-因子則是包含圖中的所有頂點之環的集合。 Bondy, John Adrian; Murty, U. S. R., Graph

Web Resource. （页面存档备份，存于互联网档案馆） Holyer, Ian, The NP-completeness of edge-coloring, SIAM Journal on Computing, 1981, 10: 718–720 . Sanders, Daniel P.;

cardinality matching）。 完全二分图 K n , n {\displaystyle K_{n,n}} 具有正则的n-边染色（英语：Edge coloring）。 完全二分图 K m , n {\displaystyle K_{m,n}} 有mn-1 nm-1个不同的生成树。 圈图（英语：Circle

Nishizeki, Takao; Kariv, Oded; Leven, Daniel; Terada, Osamu, Algorithms for edge-coloring graphs, Tech. Report TRECIS-8501, Tohoku University, 1985 

图着色问题（英語：Graph Coloring Problem，簡稱GCP），又称着色问题，是最著名的NP-完全问题之一。 给定一个无向图 G = ( V , E ) {\displaystyle G=(V,E)} ，其中 V {\displaystyle V} 为顶点集合， E {\displaystyle