엣지 컬러링

그래프 이론에서 그래프의 가장자리 색상은 그래프의 가장자리에 "색상"을 할당하여 두 입사 가장자리의 색상이 같지 않도록 하는 것이다. 예를 들어, 오른쪽 그림은 그래프의 가장자리 색상을 빨강, 파랑, 초록색으로 보여준다. 가장자리 색상은 여러 가지 다른 유형의 그래프 색소 중 하나이다. 가장자리 색상 문제는 주어진 그래프 가장자리에 k의 다른 색상을 사용하여, 주어진 k의 값에 대해 또는 가능한 가장 적은 색상으로 색칠할 수 있는지 여부를 묻는다. 주어진 그래프의 가장자리에 필요한 최소 색상 수를 그래프의 색지수라고 한다. 예를 들어 그림에서 그래프의 가장자리는 3가지 색상으로 채색할 수 있지만 2가지 색상으로 채색할 수는 없으므로 표시된 그래프에는 색지수 3이 있다.

바이징의 정리로는, 간단한 그래프의 색을 가장자리 색상에 필요한 색의 수가 최대도 Δ 또는 Δ+1이다. 초당적 그래프와 고차원 평면 그래프와 같은 일부 그래프의 경우 색의 수는 항상 Δ이고, 다중 그래프의 경우 색의 수는 3Δ/2만큼 클 수 있다. 초당적 그래프의 최적 색상을 구성하는 다항 시간 알고리즘과 최대 Δ+1 색상을 사용하는 비-비-비-비-바타이트 단순 그래프의 색상이 있지만, 최적 에지 색상을 찾는 일반적인 문제는 NP-hard이며 가장 빨리 알려진 알고리즘은 기하급수적인 시간이 걸린다. 가장자리에 대한 색상 배정이 인접하지 않은 조건 이외의 다른 조건을 충족해야 하는 에지 색상 문제의 많은 변형이 연구되었다. 에지 색상은 스케줄링 문제와 광섬유 네트워크에 대한 주파수 할당에 응용된다.

예

사이클의 길이가 짝수인 경우 사이클 그래프의 가장자리는 두 가지 색상으로 채색될 수 있다. 즉, 단순히 사이클을 중심으로 두 가지 색상을 바꾸면 된다. 다만 길이가 홀수일 경우 3가지 색상이 필요하다.^[1]

정점이 n인 완전한 그래프 K는_n n이 짝수일 때 n - 1 색상으로 가장자리를 채색할 수 있다. 이것은 Baranyai의 정리의 특별한 경우다. 소이퍼(2008)는 다음과 같은 색상의 기하학적 구조를 제공한다: n 점을 정규 (n - 1)면 다각형의 정점과 중심에 배치한다. 각 색상 클래스에 대해 중심에서 폴리곤 정점 중 하나로 가는 하나의 가장자리 및 폴리곤 정점 쌍을 연결하는 모든 수직 가장자리를 포함하십시오. 그러나 n이 홀수일 때는 n개의 색상이 필요하다. 각 색상은 총수의 1/n인 (n - 1)/2 에지에 대해서만 사용할 수 있다.^[2]

몇몇 저자들은 정점이 2n - 1명 풀에서 선택된 n - 1명의 팀을 나타내고, 가장자리가 이들 팀의 가능한 쌍을 나타내는 이상한 그래프, n-정규 그래프의 가장자리 색상을 연구했다. n = 3인 경우는 잘 알려진 피터슨 그래프를 제공한다. Biggs(1972)가 문제(n = 6)를 설명하듯이 선수들은 각 팀이 일요일을 쉬는 요일별로 6경기를 치르는 등 이들 짝짓기 일정을 찾기를 원하고 있다. 즉, 수학적으로 문제를 공식화하면 6-정규 홀수 그래프 O를₆ 6-에지로 채색한 것을 찾는다. n이 3, 4, 8일 때는 O의_n 엣지 컬러링에 n + 1 컬러가 필요하지만 5, 6, 7일 때는 n 컬러만 있으면 된다.^[3]

정의들

정점 상대와 마찬가지로, 그래프의 가장자리 색상은 아무런 조건 없이 언급될 때 항상 가장자리의 적절한 색상으로 가정되며, 이는 인접한 두 가장자리의 색상이 동일한 색상으로 지정되지 않는다는 것을 의미한다. 여기서 두 개의 뚜렷한 가장자리는 공통 정점을 공유할 때 인접하는 것으로 간주된다. 그래프 G의 가장자리 색상은 G의 모든 가장자리 및 G의 인접 가장자리 쌍에 대한 가장자리가 있는 그래프인 선 그래프 L(G)의 정점 색상과 동등하다고 생각할 수 있다.

k 다른 색을 가진 적절한 가장자리 색상을 (적절한) k-edge-coloring이라고 한다. k-edge-coloring을 할당할 수 있는 그래프는 k-edge-colorable이라고 한다. 그래프 G의 (적절한) 에지 컬러링에 필요한 가장 작은 색상은 색지수, 즉 에지 색도 번호인 ′((G)이다. 색지수 역시 표기법 χ₁(G)을 사용하여 표기하기도 하는데, 이 표기법에서 첨자 1은 가장자리가 1차원 객체임을 나타낸다. 그래프는 색 지수가 정확히 k이면 k-edge-chromatic이다. 색도 지수는 G의 적절한 정점 색상에 필요한 색의 최소 개수인 색수 χ(G)또는 χ0(G)와 혼동해서는 안 된다.

달리 명시되지 않는 한, 두 개 이상의 가장자리가 동일한 엔드포인트 쌍을 연결하고 자체 루프가 있을 수 있는 다중 그래프와 대조적으로 모든 그래프는 단순하다고 가정한다. 엣지 컬러링의 많은 문제에서, 간단한 그래프는 다중그래프와 다르게 작용하며, 간단한 그래프의 가장자리 색상에 대한 이론을 다중그래프 케이스로 확장하기 위해 추가적인 주의가 필요하다.

일치 관계

그래프 G의 일치는 가장자리의 집합으로 둘 중 어느 것도 인접해 있지 않다. 완벽한 일치는 그래프의 모든 정점에 닿는 에지를 포함하는 일치가 되며, 최대 일치는 가능한 많은 에지를 포함하는 일치가 된다. 가장자리 색상에서, 한 가지 색상이 있는 가장자리 세트는 모두 서로 인접하지 않아야 하므로, 서로 일치를 형성한다. 즉, 적절한 가장자리 색상은 그래프의 분할된 부분과 같은 것이다.

주어진 그래프에서 최대 일치의 크기가 작을 경우, 그래프의 모든 가장자리를 덮기 위해 많은 일치 항목이 필요할 것이다. 좀 더 공식적으로 표현하면, 이 추론은 만약 그래프에 총 m 가장자리가 있고, 만약 최대 β 가장자리가 최대 일치에 속할 수 있다면, 그래프의 모든 가장자리 색상은 적어도 m/β 다른 색상을 사용해야 한다는 것을 의미한다.^[4] 예를 들어, 그림에 표시된 16-Vertex 평면 그래프의 에지는 m = 24이다. 이 그래프에서, 완벽한 일치는 있을 수 없다. 중심 꼭지점이 일치한다면, 나머지 일치하지 않는 정점들은 정점수가 4개, 5개, 5개인 서로 다른 세 개의 연결된 구성요소로 분류될 수 있고, 정점 수가 홀수인 구성요소는 완벽하게 일치될 수 없다. 단, 그래프에는 에지가 7개인 최대 일치가 있으므로 β = 7이다. 따라서 그래프의 가장자리를 색칠하는 데 필요한 색의 수는 최소 24/7이고, 색의 수는 정수여야 하므로 최소 4개 이상이다.

완벽한 일치가 없는 도 k의 일반 그래프의 경우, 이 하한을 사용하여 적어도 k + 1 색상이 필요하다는 것을 보여줄 수 있다.^[4] 특히 정점 수가 홀수인 일반 그래프(예: 홀수 완성 그래프)의 경우 그러하며, 이러한 그래프의 경우 손떨림 보조정리법에 의해 k는 그 자체가 짝수여야 한다. 그러나 불평등 χ′ / m/β는 모든 정규 그래프의 색도 지수를 완전히 설명하지 못하는데, 이는 완벽한 일치를 갖지만 k-edge 색상은 가능하지 않은 정규 그래프가 있기 때문이다. 예를 들어 피터슨 그래프는 m = 15이고 완벽한 일치에 β = 5 에지가 있는 정규 그래프지만 3-에지 색상은 없다.

정도와의 관계

비징의 정리

The edge chromatic number of a graph G is very closely related to the maximum degree Δ(G), the largest number of edges incident to any single vertex of G. Clearly, χ′(G) ≥ Δ(G), for if Δ different edges all meet at the same vertex v, then all of these edges need to be assigned different colors from each other, and that can only be possible if there 적어도 Δ 색상을 할당할 수 있다. Vizing's theorem (named for Vadim G. Vizing who published it in 1964) states that this bound is almost tight: for any graph, the edge chromatic number is either Δ(G) or Δ(G) + 1. When χ′(G) = Δ(G), G is said to be of class 1; otherwise, it is said to be of class 2.

모든 초당적 그래프는 1등급이고,^[5] 거의 모든 랜덤 그래프는 1등급이다.^[6] 그러나 임의 그래프가 클래스 1인지 여부를 확인하는 것은 NP 완료다.^[7]

Vizing(1965)은 최소 8도의 평면 그래프가 1등급임을 증명했고, 최대 도 7 또는 6도의 평면 그래프도 동일하다고 추측했다. 반면에, 2등급부터 5등급까지의 최대 수준의 평면 그래프가 존재한다. 그 추측은 그 후 최대 7도의 그래프에 대해 입증되었다.^[8] 브리지리스 평면 입방형 그래프는 모두 1등급이다. 이것은 4가지 색상 정리의 동등한 형태다.^[9]

정규 그래프

k-정규 그래프를 1-요인화하여 그래프 가장자리의 분할을 완벽하게 일치시키는 것은 그래프의 k-edge-coloring과 같은 것이다. 즉, 정규 그래프는 클래스 1인 경우에만 1-요인화를 가진다. 이것의 특별한 경우로서 입방(3정규) 그래프의 3엣지 색상을 태트 색소라고 부르기도 한다.

모든 일반 그래프가 1-요인을 갖는 것은 아니다. 예를 들어, Petersen 그래프는 그렇지 않다. 보다 일반적으로 스나크는 피터슨 그래프와 마찬가지로 브리지리스, 3-정규, 2등급의 그래프로 정의된다.

Kőnig(1916년)의 정리에 따르면, 모든 초당적 정규 그래프는 1-요인을 가진다. 그 정리는 앞서 투사적 구성의 측면에서 언급되었고 에른스트 슈타이니츠에 의해 증명되었다.

멀티그래프

여러 개의 평행 가장자리가 동일한 두 꼭지점을 연결할 수 있는 다중 글자의 경우, Vizing의 정리와는 유사하지만 약한 결과는 평행 가장자리 묶음에서 최대 Δ(G), Δ(G) 및 μ(G) 에지 최대 수인 에지 색소(G)와 관련하여 알려져 있다. Vizing의 정리가 멀티그램으로 일반화되지 않는다는 것을 보여주는 간단한 예로서, 세 쌍의 정점을 각각 연결하는 세 개의 정점 및 세 개의 μ(G) 평행 가장자리의 다발인 섀넌 멀티그램(Shannon 멀티그램)을 고려한다. 이 예에서 Δ(G) = 2μ(G) (각 정점은 μ(G) 평행 에지의 3 묶음 중 2개만 입사하지만, 에지 색도 수는 3μ(G)이다(총 3μ(G) 에지가 있고, 두 에지마다 인접하므로 모든 에지는 서로 다른 색상을 할당해야 한다. In a result that inspired Vizing,^[10] Shannon (1949) showed that this is the worst case: χ′(G) ≤ (3/2)Δ(G) for any multigraph G. Additionally, for any multigraph G, χ′(G) ≤ Δ(G) + μ(G), an inequality that reduces to Vizing's theorem in the case of simple graphs (for which μ(G) = 1).

알고리즘

그래프가 클래스 1인지 여부를 테스트하는 문제는 NP-완전성이기 때문에 최적의 색상 수로 모든 그래프를 에지 색상으로 채색하기 위한 알려진 다항 시간 알고리즘이 없다. 그럼에도 불구하고, 이러한 기준들 중 하나 이상을 완화시키는 많은 알고리즘이 개발되었다: 그것들은 그래프의 부분집합에서만 작동하거나, 항상 최적의 수의 색상을 사용하지 않거나, 항상 다항식 시간에 실행되지 않는다.

그래프의 특수 클래스에 최적의 색칠

최대 Δ가 있는 초당적 그래프나 다중 그래프의 경우, 색의 최적 개수는 정확히 Δ이다. Cole, Ost & Schirra(2001)는 이러한 그래프의 최적 에지 색상은 거의 선형 시간 경계 O(m log Δ)에서 찾을 수 있다는 것을 보여주었는데, 여기서 m은 그래프에 있는 에지의 수입니다. 단순하지만 다소 느린 알고리즘은 Cole & Hopcroft(1982)와 Alon(2003)에 의해 설명된다. Alon(2003)의 알고리즘은 입력 그래프를 그 정도를 증가시키거나 크기를 유의하게 증가시키지 않고 규칙적으로 만드는 것으로 시작하는데, 이는 초당파의 같은 쪽에 속하는 정점 쌍을 병합한 다음 소수의 추가 정점과 가장자리를 추가하는 것이다. 그 후, 정도가 홀수일 경우, 알론은 거의 선형에 가까운 시간에 하나의 완벽한 일치를 찾아내어 색상을 할당하고 그래프에서 제거하여 정도가 균등해지도록 한다. 마지막으로 알론은 Gabow(1976년)의 관찰을 적용하여, 그래프 투어의 오일러에서 가장자리의 서브셋을 교대로 선택하면 가장자리 색소 문제가 두 개의 더 작은 하위 문제로 분할되고, 그의 알고리즘은 두 개의 하위 문제를 반복적으로 해결한다. 그의 알고리즘의 총 시간은 O(m log m)이다.

최대 Δ Δ 7을 갖는 평면 그래프의 경우, 색의 최적 개수는 다시 정확히 Δ이다. Δ ≥ 9라고 더 강한 가정으로, 선형 시간(Cole & Kowalik 2008)에서 최적의 가장자리 색소를 찾을 수 있다.

인접 행렬이 최대 d에서^1−ε 두 번째로 큰 고유값(절대값)을 갖는다는 점에서 의사 랜덤 그래프인 d-정규 그래프의 경우 d가 최적의 색상 수입니다(Ferber & Jain 2018).

최적의 색상 수 이상을 사용하는 알고리즘

Misra & Gries(1992)와 Gabow 외 연구진(1985)은 Vizing의 정리에 의해 주어진 바운드를 충족하면서 모든 그래프를 Δ + 1 색상으로 채색하기 위한 다항 시간 알고리즘을 설명한다. Misra & Gries 엣지 컬러링 알고리즘을 참조한다.

멀티그래프의 경우 카를로프&쇼모이스(1987)는 다음과 같은 알고리즘을 제시하는데, 이 알고리즘은 일라이 업팔의 덕택이다. 모든 홀수도의 꼭지점에 가장자리로 연결된 새 꼭지점을 추가하여 입력 다중그래프 G 오일러안을 만들고 오일러 투어를 찾은 다음 투어를 위한 방향을 선택하십시오. 지향적인 투어가 G에서 u에서 v까지 엣지를 가질 때마다 양분 왼쪽의 꼭지점 u에서 오른쪽의 꼭지점 v까지 에지를 가진 G의 각 꼭지점에 각각 하나씩 2개의 복사본이 있는 초당적 그래프 H를 형성한다. 각 Colo에 초당적 그래프 가장자리 색소 알고리즘을 적용한다.r class in H는 최대 °2의 서브그래프를 형성하는 G의 엣지 집합에 해당한다. 즉, 경로와 주기의 분리 결합을 형성하기 때문에 H의 각 색상 클래스에 대해 G의 세 가지 색상 클래스를 구성할 수 있다. 알고리즘의 시간은 Cole, Ost & Schirra(2001)의 알고리즘을 사용한 초당적 그래프 O(m 로그 Δ)의 에지 색상에 의해 제한된다. The number of colors this algorithm uses is at most ${\displaystyle 3\left\lceil {\frac {\Delta }{2}}\right\rceil }$, close to but not quite the same as Shannon's bound of ${\displaystyle \left\lfloor {\frac {3\Delta }{2}}\right\rfloor }$. It may also be made into a parallel algorithm in a straightforward way 같은 논문에서 카를로프와 슈모이스는 또한 최대 3도 멀티그래프를 4가지 색상으로 채색하는 선형 시간 알고리즘을 제시하는데, 이 알고리즘은 새로운 정점을 추가해 그래프를 오일러 투어를 만든 다음, 가장자리 세트를 번갈아 선택한다. 그래프를 최대 2도의 두 개의 하위 그래프로 분할하는 투어에서. 각 서브그래프의 경로와 짝수 사이클은 서브그래프당 두 가지 색상으로 색칠할 수 있다. 이 단계 후, 각각의 남은 홀수 사이클은 반대편 서브그래프에 속하는 두 가지 색상 중 하나로 색칠될 수 있는 적어도 하나의 가장자리를 포함한다. 홀수 사이클에서 이 가장자리를 제거하면 경로가 남는데, 이 경로는 서브그래프에 두 가지 색상을 사용하여 색칠할 수 있다.

그래프 또는 다중 글자의 가장자리를 하나씩 고려하여 사용 가능한 첫 번째 색상을 각 가장자리에 할당하는 탐욕스러운 색상 알고리즘은 때때로 필요한 색상의 거의 두 배인 2Δ - 1 색상을 사용할 수 있다. 단, 입력 그래프를 미리 알 수 없는 온라인 알고리즘 설정에 사용할 수 있다는 장점이 있다. 이 설정에서는 경쟁률이 2이며, 이는 다른 온라인 알고리즘으로는 더 나은 성능을 얻을 수 없다는 것이 최적이다.^[11] 단, 가장자리가 랜덤 순서로 도착하고 입력 그래프가 최소한 로그적인 정도를 가지면 더 작은 경쟁률을 달성할 수 있다.^[12]

여러 저자들은 모든 다중 글자의 부분 색도 지수(선형 프로그래밍을 사용하여 다항식 시간으로 계산할 수 있는 숫자)가 색도 지수 중 하나 안에 있음을 암시하는 추측을 해 왔다.^[13] 만약 이러한 추측이 사실이라면, 간단한 그래프에 대해 바이징의 정리를 통해 알려진 것과 일치시키면서, 다문자의 경우 색지수에서 결코 1 이상 떨어져 있지 않은 숫자를 계산할 수 있을 것이다. 일반적으로 입증되지는 않았지만, 이러한 추측들은 색도 지수가 최소한 $\Delta {\displaystyle \mathrm{}}$+ ${\displaystyle \Delta \sqrt{\mathrm{}}}$/ ${\displaystyle \sqrt{2\mathrm{}}}$ ${\$일 때 충분히 큰 다문자에 일어날 수 있는 것으로 알려져 있다$.$^[14]

정확한 알고리즘

그래프가 하나 또는 두 가지 색상으로 가장자리 색상을 가질 수 있는지 테스트하는 것은 간단하기 때문에 가장자리 색상의 첫 번째 경우는 그래프에 3-엣지 색상이 있는지 테스트하는 것이다. 코왈릭(2009)이 보여주듯 다항식 공간만 사용하면서 시간 O(1.344ⁿ)로 3엣지 색상이 있는지 테스트할 수 있다. 비록 이 시간 한계가 기하급수적이긴 하지만, 그것은 색의 가장자리에 대한 모든 가능한 할당에 대해 맹수적인 힘 검색보다 훨씬 더 빠르다. Every biconnected 3-regular graph with n vertices has O(2^n/2) 3-edge-colorings; all of which can be listed in time O(2^n/2) (somewhat slower than the time to find a single coloring); as Greg Kuperberg observed, the graph of a prism over an n/2-sided polygon has Ω(2^n/2) colorings (lower instead of upper bound), showing that this bound is tight.^[15]

입력 그래프의 선 그래프에 정점 채색에 대한 정확한 알고리즘을 적용함으로써 필요한 색의 수에 관계없이 시간 2m와^mO(1) 지수 공간 또는 시간 O(2.2461^m)에 상관없이 모든 그래프를 최적의 에지 색상으로 색칠할 수 있으며 다항 공간(Björklund, Husfelt & Koivisto 2009)만 가능하다.

엣지 컬러링은 3가지 색상에도 NP가 완성되기 때문에 색상 수로 파라메트릭을 했을 때 고정 파라미터를 추적할 수 있을 것 같지 않다. 그러나 다른 매개변수에 대해서는 추적할 수 있다. 특히 저우, 나카노, 니시제키(1996)는 나무 너비 w의 그래프의 경우 최적의 에지 색상을 시간 O(6w)로 계산할 수 있다는 것을 보여주었는데,^{w(w + 1)/2} 이 바운드는 그래프에 있는 정점 수 n에만 선형적으로 의존한다.

Nemhauser & Park(1991)은 엣지 컬러링 문제를 정수 프로그램으로 공식화하고, 엣지 컬러 그래프에 엣지 프로그래밍 솔버를 사용한 경험을 설명한다. 그러나 그들은 알고리즘의 복잡성 분석을 수행하지 않았다.

추가 속성

그래프는 색상의 k! 가능한 순열을 무시하고 가장자리를 k 색상 등급으로 분할하는 한 가지 방법만 있는 경우 독특하게 k-edge 색상이 가능하다. k ≠ 3의 경우 유일한 고유 k-edge 색상이 가능한 그래프는 경로, 주기 및 별이지만 k = 3의 다른 그래프도 고유하게 k-edge 색상이 될 수 있다. 모든 고유 3-엣지-컬러블 그래프는 정확히 3개의 해밀턴 사이클(세 가지 색상 등급 중 하나를 삭제하여 형성된 그래프)이 있지만, n ≥ 2에 대해 일반화된 피터슨 그래프 G(6n + 3, 2)와 같이 3-컬러블이 아닌 3-컬러블 그래프가 존재한다. 유일하게 알려진 비플래너 고유 3색 그래프는 일반화된 피터슨 그래프 G(9,2)로, 다른 그래프는 존재하지 않는다고 추측했다.^[16]

포크맨&풀커슨(1969)은 첫 번째 색상의 m 가장자리₁, 두 번째 색상의 m₂ 가장자리 등을 가진 주어진 그래프 G의 적절한 가장자리 색상이 존재한다는 속성으로 숫자₁ m, m₂, m₃, m, ...의 증가하지 않는 시퀀스를 조사했다. 그들은 이러한 의미에서 시퀀스 P가 실현 가능하고, 동일한 합을 가진 시퀀스 Q보다 사전 편찬 순서에서 더 큰 경우 Q도 실현 가능하다고 보았다. 왜냐하면, 사전순으로 P > Q가 나오면, P는 일련의 스텝에 의해 Q로 변형될 수 있는데, 각 스텝은 숫자_i m을 한 단위씩 줄이고, i < j를 한 단위씩으로 하여 이후의 숫자 m을_j 증가시킨다. 엣지 컬러링의 측면에서 P를 실현하는 컬러링으로부터 시작하여, 이 같은 각각의 단계는 두 컬러를 번갈아 가며 켐페 체인의 최대 에지 경로인 컬러 i와 j를 스와핑하여 수행할 수 있다. 특히 모든 그래프는 동일한 가장자리 색상을 가지며, 두 가지 색상 등급마다 크기가 최대 한 단위씩 다른 최적의 색상을 가진 가장자리 색상을 가진다.

De Bruijn-Erdős 정리를 사용하여 유한 그래프의 많은 에지 색소 특성을 무한 그래프로 전송할 수 있다. 예를 들어, 섀넌과 바이징의 색채 지수에 대한 그래프의 정도와 관련된 이론들은 모두 무한 그래프에 직접적으로 일반화된다.^[17]

리히터(2011년)는 도면의 모든 가장자리가 서로 다른 세 개의 경사 중 하나를 가지며 두 개의 가장자리가 서로 같은 선에 있지 않다는 특성을 가진 주어진 입방형 그래프의 그래프 도면을 찾는 문제를 고려한다. 이러한 도면이 존재할 경우, 그래프의 3-엣지 색상에서 가장자리의 기울기를 색상으로 사용할 수 있다. 예를 들어, 일반 육각형의 가장자리와 긴 대각선으로서의 유틸리티 그래프_3,3 K의 도면은 이러한 방식으로 그래프의 3-엣지 색상을 나타낸다. 리히터가 보여주듯이, 주어진 Tait 색상이 있는 3정규의 단순 초당적 그래프는 3엣지 연결인 경우에만 주어진 색상을 나타내는 도면을 가지고 있다. 비-비-비-바타이트 그래프의 경우 조건이 좀 더 복잡하다. 즉, 그래프의 초당적 이중 커버가 3-엣지로 연결되고, 단색 쌍을 삭제하면 여전히 비-바타이트인 서브그래프로 이어지는 경우, 주어진 색상은 도면으로 나타낼 수 있다. 이러한 조건들은 모두 다항식 시간에 쉽게 시험될 수 있지만, 4-엣지 색상의 4-정규 그래프가 경사별로 색을 나타내는 4-경사선의 가장자리가 있는 도면을 가지고 있는지 시험하는 문제는 실체들의 실존 이론에 대해 완전한 것으로서, 적어도 NP-완전성만큼이나 어려운 복잡성 등급이다.

색도 지수는 그래프의 최대 도 및 최대 일치 수와 관련이 있을 뿐만 아니라 그래프 가장자리가 분할될 수 있는 최소 선형 포리스트 수(경로의 분리 결합)인 그래프 G의 선형 수목성 la(G)와 밀접하게 관련되어 있다. 매칭은 특별한 종류의 선형 숲이며, 다른 방향에서는 어떤 선형 숲이라도 2엣지 색상이 될 수 있기 때문에, 모든 G에 대해 la(G) ≤′(G) ≤ 2(G) 2 2 la(G)를 따른다. Akiyama's conjecture (named for Jin Akiyama) states that ${\displaystyle \mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {\Delta +1}{2}}\right\rceil }$, from which it would follow more strongly that 2 la(G) − 2 ≤ χ′(G) ≤ 2 la(G). 최대도 3의 그래프의 경우 la(G)는 항상 정확히 2이므로 이 경우 바운드 bound bound(G) ) 2 la(G)는 바이징의 정리에서 주어진 바운드와 일치한다.^[18]

기타유형

그래프의 Thue 번호는 모든 짝수 길이 경로에서 경로의 첫 번째 절반과 두 번째 절반은 다른 색상 순서를 형성하는 더 강력한 요건을 충족하는 가장자리 색상에 필요한 색상 수입니다.

그래프의 수목성은 각 색상의 가장자리에 주기가 없도록 필요한 최소 색상 수입니다(표준 가장자리 색소 문제에서 인접한 가장자리 쌍이 없는 것이 아님). 즉, 그래프의 가장자리가 분할될 수 있는 최소 포리스트 수입니다.^[19] 색지수와는 달리, 그래프의 수목성은 다항 시간으로 계산될 수 있다.^[20]

목록 가장자리 색상은 각 가장자리가 색상 목록과 연관되는 그래프가 주어지는 문제로, 각 가장자리의 색상이 해당 가장자리 목록에서 그려지는 적절한 가장자리 색상을 찾아야 한다. 그래프 G의 목록 색지수는 가장자리에 대한 색상 목록을 어떻게 선택하든 각 가장자리의 색상이 목록에 적어도 k개 이상 있는 한 색상이 보장되는 특성을 가진 가장 작은 수 k이다. 따라서 리스트 색도 지수는 최소한 색도 지수만큼 항상 크다. 부분적인 라틴어 영역의 임무 완수에 그 Dinitz 추측은 목록 edge Kn,n의 간선 채색 수와 같습니다 완전한 양분 그래프의 색 수,n. 갤빈(1995년), 더 일반적으로 말해서, 모든 양분 그래프에서 색채 지수 및 목록 색 색인을 당황 추측을 해결했다로 rephrased 수 있다. 함께e 대등하다 색도 지수와 목록 색도 지수의 동일성은 일반적으로 자가 루프가 없는 임의의 다중 글자에 대해 더 일반적으로 유지될 것으로 추측되었다. 이러한 추측은 여전히 열려 있다.

일반적으로 연구된 정점 색상의 다른 많은 변화들도 가장자리 색상으로 확장되었다. 예를 들어, 완전 모서리 색상은 완전 모서리 색상의 변종이며, 각 한 쌍의 색상이 적어도 한 쌍의 인접 모서리들로 표현되어야 하며, 총 색상 수를 최대화하는 것이 목표인 적절한 모서리 색이다.^[21] 강한 가장자리 색상은 강한 가장자리 색상의 변형이며, 가장자리 색상은 인접한 끝점을 가진 두 가장자리마다 다른 색상을 가져야 한다.^[22] 강한 가장자리 색상은 무선 네트워크에 대한 채널 할당 체계에 응용된다.^[23]

가장자리 색상은 가장자리 색상의 변종이며, 가장자리 색상은 두 가지 색 등급마다 가장자리 색상이 반복 하위그래프(즉, 숲)를 형성한다.^[24] The acyclic chromatic index of a graph ${\displaystyle G}$, denoted by ${\displaystyle a'(G)}$, is the smallest number of colors needed to have a proper acyclic edge coloring of ${\displaystyle G}$. It has been conjectured that ${\displaystyle a'(G)\leq \Delta +2}$, where ${\displa$$ystyle \Delta }$ is the maximum degree of ${\displaystyle G}$.^[25] Currently the best known bound is ${\displaystyle a'(G)\leq \lceil 3.74(\Delta -1)\rceil }$.^[26] The problem becomes easier when ${\displaystyle G}$ has large girth. More specifically, there is a constant ${\displaystyle c}$ such that if the girth of ${\displaystyle G}$ is at least ${\displaystyle c\Delta \log \Delta }$, then ${\displaystyle a'(G)\leq \Delta +2}$.^[27] A similar result is that for all ${\displaystyle \epsilon >0}$ there exists an ${\displaystyle g}$ such that if ${\displaystyle G}$ has girth at least ${\displaystyle g}$, then ${\displaystyle a'(G)\leq (1+\epsilon )\Delta }$.^[28]

엡스타인(2013년)은 두 가지 색소 주기가 서로 단일 에지 이상을 공유하지 않는 추가 속성으로 입방 그래프의 3 에지 색상을 연구했다. 그는 그러한 색상의 존재는 좌표 축과 평행한 가장자리와 각 축 평행선이 최대 두 정점을 포함하는 3차원 정수 격자 위에 그래프의 도면이 존재하는 것과 동등하다는 것을 보여주었다. 그러나, 표준 3-엣지컬링 문제와 마찬가지로, 이러한 유형의 색상을 찾는 것은 NP-완전하다.

토탈 컬러링은 정점과 가장자리를 모두 컬러링하도록 요구하여 정점과 가장자리 컬러링을 결합한 컬러링의 일종이다. 정점과 가장자리 또는 가장자리와 가장자리의 모든 입사 쌍은 인접한 두 정점처럼 뚜렷한 색을 가져야 한다. 어떤 그래프가 색의 수가 최대 도 + 2인 총 색상을 가지고 있다고 추측되어 왔으나(비징의 정리와 브룩스의 정리를 합친 것) 이것은 입증되지 않은 채로 남아 있다.

표면의 3-정규 그래프가 3-엣지 색상인 경우, 이중 그래프는 모든 삼각형이 각 색의 한 모서리를 가질 수 있도록 에지 색상(일반적으로 적절한 에지 색상은 아님)도 표면의 삼각형을 형성한다. 삼각형의 정점 또는 면에 색상이 배열되는 방법에 대한 다른 국부적 제약조건과 함께 다른 삼각형의 색상과 방향은 여러 유형의 기하학적 객체를 인코딩하는 데 사용될 수 있다. 예를 들어, 직사각형 구획(직사각형 구획을 더 작은 직사각형으로 나눈 부분, 3개의 직사각형이 모든 정점에서 만나는 경우)은 각 정점에 발생하는 제약조건과 함께 구획에 이중으로 삼각형의 가장자리를 두 가지 색상으로 표시한 "정규 라벨링"으로 조합하여 설명할 수 있다.각각의 색상이 동일한 연속적인 부분들. 이 라벨링은 수직 가장자리가 한 색이고 수평 가장자리가 다른 색인 직사각형 부분 자체의 색상에 이중적이다. 정점 주위에 색상의 가장자리가 나타날 수 있는 순서에 따라 유사한 국부적 제약조건을 사용하여 평면 그래프와 축 평행 면이 있는 3차원 다면체의 직선 그리드 임베딩을 인코딩할 수도 있다. 이 세 가지 유형의 정규 레이블링에 대해 고정 그래프의 정규 레이블 세트는 동일한 그래프(예: 동일한 골격을 가진 모든 축 평행 다면체)에 기초한 모든 기하학적 구조를 신속하게 나열하거나 추가 제약 조건을 충족하는 구조를 찾는 데 사용할 수 있는 분배 격자를 형성한다.^[29]

결정론적 유한 자동화는 각 꼭지점이 동일한 아웃도 d를 가지며, 동일한 소스 꼭지점을 가진 두 가장자리마다 구별되는 색상을 갖는 방식으로 가장자리가 d-색인 방향 그래프로 해석될 수 있다. 도로 채색 문제는 결과적인 자동화가 동기화 단어를 가질 수 있도록 지시된 그래프를 균일한 아웃도어로 색칠하는 문제다. 트라트만(2009)은 주어진 그래프가 강하게 연결되어 있고 주기적인 색상이 있을 때마다 그러한 색상을 발견할 수 있다는 것을 증명함으로써 도로 색소 문제를 해결했다.

램지의 정리는 주어진 크기 s의 단색적 완전 하위 그래프_s K를 생성하지 않기 위해 대형 전체 그래프_n K의 가장자리를 k-컬러링하는 문제를 다룬다. 정리에 따르면, n ≥ R(s)이 있을 때마다 그러한 색상은 가능하지 않은 숫자 R_k(s)이 존재한다. 예를 들어 R₂(3) = 6, 즉 그래프 K의₆ 가장자리가 2색이면 항상 단색 삼각형이 있게 된다.

가장자리 색의 그래프의 길은 색깔이 반복되지 않으면 무지개 길이라고 한다. 그래프는 어떤 두 쌍의 꼭지점 사이에 무지개 경로가 있으면 무지개 색이라고 한다. 그래프 G의 색상이 1. . t인 가장자리 색상은 모든 색상이 사용되는 경우 간격 t 색상으로, G의 각 꼭지점에 발생하는 가장자리 색상은 구별되며 정수의 간격을 형성한다.

적용들

전체 그래프의 가장자리 색상은 라운드 로빈 토너먼트를 가능한 한 적은 라운드로 예약하여 각 선수 쌍이 라운드 중 한 라운드에서 서로 플레이하도록 할 수 있다. 이 애플리케이션에서 그래프의 정점은 토너먼트에서 선수에 해당하고, 가장자리 색상은 게임에 해당하며, 가장자리 색상은 다음 라운드에 해당한다. 경기가 열리는 ^[30]라운드 예를 들어, 미식축구의 경우, 특정 해에 서로 경기할 팀 쌍을 전년도 팀 기록에 기초하여 결정하고, 그 다음 형성된 그래프에 엣지 컬러링 알고리즘을 적용하는 등, 유사한 컬러링 기술을 사용하여 모든 플레이가 아닌 다른 스포츠 페어링을 스케줄링할 수도 있다. 게임을 플레이하는 주말에 할당하기 위해 페어링 집합에 의해.^[31] 이 어플리케이션의 경우, 바이징의 정리는 어떤 페어링 세트를 선택해도(같은 시즌에 서로 2번 경기하는 팀이 없는 한), 팀당 경기가 있는 것보다 최대 주말 한 번 더 사용하는 스케줄을 항상 찾을 수 있다는 것을 내포하고 있다.

오픈 숍 스케줄링은 생산 공정 스케줄링의 문제로서, 제조할 물체 집합이 있고, 각 물체는 (어떤 순서로든) 그 위에서 수행할 작업 집합이 있으며, 각 작업은 특정 기계에서 수행되어야 하며, 동일한 기계가 동시에 수행되어야 하는 다른 작업을 방지해야 한다. 모든 과제의 길이가 같은 경우, 이 문제는 초당적 다중 글씨를 색칠하는 가장자리 중 하나로 공식화될 수 있다. 이 경우, 초당적 분할의 한쪽 정점은 제조할 물체를 나타내고, 양립의 반대쪽 정점은 제조 기계를 나타내며, 가장자리는 수행되어야 하는 과제를 나타낸다.d, 그리고 색상은 각 작업이 수행될 수 있는 시간 단계를 나타낸다. 초당적 가장자리 색상은 다항식 시간에 수행될 수 있으므로, 오픈 숍 스케줄링의 제한된 경우에도 마찬가지다.^[32]

간덤, 다완드 & 프라카시(2005)는 엣지 컬러링의 변종으로서 센서 네트워크의 시간 분할 다중 접속 네트워크 통신 프로토콜에 대한 링크 스케줄링 문제를 연구한다. 이 문제에서 네트워크의 각 노드가 간섭 없이 각 인접 노드와 통신할 수 있도록 무선 통신 네트워크의 가장자리에 대한 시간 간격을 선택해야 한다. 강한 가장자리 색상을 사용하면(그리고 각 가장자리 색상에 각각 하나씩 두 개의 시간 간격을 사용) 문제를 해결할 수 있지만 필요 이상으로 많은 시간 간격을 사용할 수 있다. 대신, 그들은 네트워크의 각 비방향 가장자리를 두 배로 늘려 형성된 지시 그래프의 색상을 구하는데, 각 방향 가장자리 UV가 v에서 나가는 가장자리 및 v의 이웃으로부터 나가는 가장자리와는 다른 색상을 가지고 있다. 그들은 서로 간섭할 수 있는 가장자리를 재조정하는 후처리 단계와 함께 (Δ + 1) 에지컬링에 대한 분산 알고리즘에 기초하여 이 문제에 대한 경험적 접근법을 제안한다.

광섬유 통신에서 경로 색소 문제는 서로 통신을 원하는 노드 쌍에 색상(광선 빈도)을 할당하고 각 쌍에 대해 광섬유 통신망을 통한 경로를 지정하는 문제로, 광섬유 부문을 공유하는 두 경로가 각각과 동일한 주파수를 사용하지 않는다는 제한을 받는다. 기타. 동일한 통신 스위치를 통과하지만 섬유 세그먼트를 통과하지 않는 경로는 동일한 주파수를 사용할 수 있다. 통신망을 별 네트워크로 배열할 때, 각각의 노드에 별도의 섬유로 연결된 단일 중앙 스위치로 경로 색소 문제는 통신 노드가 그래프 정점을 형성하는 그래프나 다중 글램의 가장자리 색소화 문제로 정확하게 모델링할 수 있다.그는 가장자리를 그래프로 표시하며, 각 쌍에 사용될 수 있는 주파수는 가장자리 색채 문제의 색을 형성한다. 보다 일반적인 트리 토폴로지를 가진 통신 네트워크의 경우, 네트워크의 각 스위치에 의해 정의된 스타 네트워크에 대한 로컬 경로 색소 솔루션을 패칭하여 단일 글로벌 솔루션을 구성할 수 있다.^[33]

문제 열기

Jensen & Toft(1995)는 가장자리 색칠과 관련된 23개의 개방형 문제를 나열한다. 여기에는 다음이 포함된다.

• 골드버그(1973)의 추측에 의하면 색채지수와 분수지수가 서로 내포되어 있어 다항 시간에서 색채지수를 한 색상 내에서 근사하게 추정할 수 있을 것이다.
• 엣지 색소를 위한 임계 그래프 구조에 대한 야콥슨 등에 대한 여러 가지 추측, 어떤 하위 그래프가 더 작은 최대도를 갖거나 1등급인 2등급 그래프. 야콥슨은 원래 모든 임계 그래프에 정점 수가 홀수라고 추측했지만, 결국 이것이 반증되었다. 이것을 약화시키거나, 혹은 중요한 그래프와 중요한 다중 글자의 정점 수를 제한하는 몇 가지 다른 추측들은 여전히 열려있다.
• 등급 2 평면 그래프에 대해 가능한 최대 도를 분류하는 Vizing의 문제.
• The overfull subgraph conjecture of A. J. W. Hilton, stating that graphs with degree at least n/3 are either of class 1 or contain a subgraph with the same degree Δ as the original graph, and with an odd number k of vertices, such that the number of edges in the subgraph is greater than Δ(k − 1)/2, and a similar conjecture by Herbert Grötzsch and P고차 그래프 대신 평면 그래프를 다루는 aul Seimour.
• 정점수가 짝수 n이고 등급이 n/2 이상인 일반 그래프가 등급 1이라는 아만다 체트윈드와 앤서니 힐튼의 추측.
• Claude Berge와 D에 대한 추측. 브리지리스타일 3-일반 단순 그래프의 모든 가장자리를 두 배로 늘려 형성된 6-정규 다중그래프는 6가지 색상으로 가장자리 색상이 될 수 있다.
• 발톱 K를_1,3 제외한 모든 삼각형이 없는 평면 그래프가 독특하게 3엣지 색상이 가능한 것은 아니라는 피오리니와 윌슨의 추측이다.
• 2012년 추론에서 G가 d-정규 평면 다문자라면 G가 이상하게도 d-엣지 연결이 되어 있는 경우에만 d-엣지 색상이 가능하다고 한다. 이 추측은 d=3에서 발생하는 4색 정리의 일반화다. 마리아 추드노브스키, 캐서린 에드워즈, 그리고 폴 시모어는 8개의 정규 평면 다문자가 가장자리 색도 수가 8이라는 것을 증명했다.^[34]

메모들

참조