토탈 컬러링

포스터 케이지의 적절한 토탈 컬러링 6가지 색상.이 그래프의 총 색수는 각 정점의 정도가 5이기 때문에 6이다. (5개의 인접 에지 + 1 꼭지점 = 6).

그래프 이론에서 토탈 컬러링은 그래프의 꼭지점과 가장자리에 있는 그래프 컬러링의 일종이다.아무런 자격요건 없이 사용할 경우, 인접한 가장자리, 정점 및 가장자리, 그리고 어느 한쪽 끝단이 동일한 색상에 할당되지 않는다는 점에서 총색상은 항상 적절하다고 가정한다.그래프 G의 총 색수 χ″(G)는 G의 전체 색상에 필요한 가장 적은 색이다.

그래프 G의 총 그래프 T = T(G)는 (i) T의 정점 세트가 G의 정점과 가장자리에 해당하고 (ii) 해당 요소가 G에 인접하거나 인시던트인 경우에만 두 정점이 T에 인접하는 그래프다.그러면 G의 전체 색상은 T(G)의 정점 색상이 된다.토탈 컬러링은 그래프의 꼭지점과 가장자리를 총 독립 집합으로 분할하는 것이다.

χ″(G)에 대한 일부 불평등:

1. χ″(G) ≥ Δ(G) + 1.
2. χ″(G) ≤ Δ(G) + 10²⁶. (몰로이, 리드 1998)
3. χ″(G) ≤ Δ(G) + 8 ln⁸(Δ(G)) Δ(G)로 충분히 큰 Δ(G). (Hind, Moloy, Reed 1998)
4. χ″(G) ≤ ch′(G) + 2

여기서 Δ(G)는 최대 도이고, ch′(G)는 가장자리 선택성이다.

토탈 컬러링은 단순히 정점과 가장자리 컬러링이 혼합된 것이기 때문에 자연스럽게 발생한다.다음 단계는 총 색도 수에서 최대 도 단위로 Brooks 유형 또는 Vizing 유형 상한선을 찾는 것이다.

최고 학위 상한의 총 채색 버전은 수학자들을 50년 동안 따돌린 어려운 문제다.A trivial lower bound for χ″(G) is Δ(G) + 1. Some graphs such as cycles of length ${\displaystyle n\not \equiv 0{\bmod {3}}}$ and complete bipartite graphs of the form ${\displaystyle K_{n,n}}$ need Δ(G) + 2 colors but no graph has been found that requires more colors.이는 모든 그래프에 Δ(G) + 1 또는 Δ(G) + 2 색상이 필요하지만 그 이상은 필요하지 않다는 추측으로 이어진다.

총 착색 추측(Behzad, Vizing).${\displaystyle \chi'(G)\leq \Delta (G)+2.$$}$

분명히 "토탈 컬러링"이라는 용어와 토탈 컬러링 추측의 문구는 1964년부터 1968년 사이에 베자드와 비징에 의해 여러 차례 독자적으로 소개되었다(Jensen & Toft 참조).이 추측은 모든 초당적 그래프와 6도가 최대인 그래프를 제외한 대부분의 평면 그래프와 같은 몇 가지 중요한 등급의 그래프를 수용하는 것으로 알려져 있다.비징의 평면 그래프 추측이 사실이라면 평면 케이스를 완성할 수 있다.또한 리스트 컬러링 추측이 사실이라면 $\chi {\displaystyle {}^{}}$(${\displaystyle }$G${\displaystyle }$)${\displaystyle \mathrm{\Delta }}$( ${\displaystyle G}$)${\displaystyle }$+ 3${\displaystyle \chi''(G)\leq \Delta (G)+3.$$}$

토탈 컬러링과 관련된 결과가 나왔다.예를 들어, Kilakos와 Reed(1993)는 그래프 G의 총 그래프의 부분 색도 수가 최대 Δ(G) + 2임을 증명했다.

참조

• Hind, Hugh; Molloy, Michael; Reed, Bruce (1998). "Total coloring with Δ + poly(log Δ) colors". SIAM Journal on Computing. 28 (3): 816–821. doi:10.1137/S0097539795294578.
• 젠슨, 토미 R;토프트, 비야른(1995)그래프 색칠 문제.뉴욕: 와일리-인터사이언스.ISBN 0-471-02865-7
• Kilakos, Kyriakos; Reed, Bruce (1993). "Fractionally colouring total graphs". Combinatorica. 13 (4): 435–440. doi:10.1007/BF01303515.
• Molloy, Michael; Reed, Bruce (1998). "A bound on the total chromatic number". Combinatorica. 18 (2): 241–280. doi:10.1007/PL00009820. hdl:1807/9465.