불량색소

그래프 이론에서, 수학적 분야인 색채는 색이나 라벨을 그래프의 꼭지점, 가장자리 및 면에 할당하는 것을 말한다.결함 있는 색상은 적절한 정점 색상의 변형이다.적절한 정점 색상에서, 정점은 인접한 정점이 동일한 색을 가지지 않도록 색상으로 칠해져 있다.반면에 결함 있는 색상에서 정점은 어느 정도 같은 색의 이웃을 가질 수 있다.(그래프 이론 용어집 참조)

역사

결함 있는 색소는 버어와 제이콥슨, 하라리와 존스와 코웬, 코웬과 우달에 의해 거의 동시에 도입되었다.^[1]이것과 관련된 색채에 대한 조사는 마리에티 프릭에 의해 주어진다.^[2]Cowen, Cowen, Woodall은 표면에 내장된 그래프에 초점을 맞추고 모든 평면도가 (k, d) 색상이 될 수 있도록 모든 k와 d의 완전한 특성을 부여했다.즉, 모든 평면 그래프가 (1, d)- 또는 (2, d)- 색상이 되는 d가 존재하지 않으며, (3, 1) 색상이 아닌 평면 그래프가 존재하지만, 모든 평면 그래프는 (3, 2) 색상이 가능하다.4색 정리가 암시하는 (4, 0) 색상과 함께, 이것은 평면의 결함 있는 색수를 해결한다.Poh와 Goddard는 모든 평면 그래프는 각 색 등급이 선형 숲인 특수(3,2) 색상이 있으며, 이는 우달의 보다 일반적인 결과에서 얻을 수 있다는 것을 보여주었다.일반 표면의 경우 $각{\displaystyle }$ 속 g ${\displaystyle \ge }$ ${\displaystyle 0}$ ${\displaystyle$ g$\geq$ 0$}$에$$대해 $k{\displaystyle }$ =${\displaystyle }$k${\displaystyle (g}$ )${\displaystyle k=k(g)}$이(가$$) 존재하므로 $속{\displaystyle }$ g ${\displaystyle g}$ 표면의 모든 그래프는 (4, k) 색상이 가능하다$$.^[1]이것은 댄 아치디콘이 색칠할 수 있는 (3, k)로 개선되었다.^[5]일반 그래프의 경우, 여러 번 재발견된 1960년대 Laszlo Lovász의 결과는 최대도 ∆의 불량 컬러링 그래프에 대한 O(∆E)-시간 알고리즘을 제공한다.

정의 및 용어

불량색소

그래프 G의 A(k, d) 색상은 각 꼭지점 v가 정점 v와 동일한 색상을 가진 대부분의 이웃을 가질 수 있도록 k 색상으로 정점을 채색한 것이다.우리는 k를 양의 정수(k = 0인 경우를 고려할 때 중요하지 않음)로 간주하고 d는 음이 아닌 정수로 간주한다.따라서 (k, 0) 색상은 적절한 정점 색상과 동일하다.^[9]

d-분광 색수

G가 (k, d)-색상 가능한 색상 k의 최소 개수를 d-결함 색도수, $\chi {\displaystyle {}_{}}$ ${\displaystyle d_{}}$(${\displaystyle G}$ ) ${\displaystyle \chi _{d}(G)}$라고 한다$.$^[10]

그래프 클래스 G의 경우, 결함이 있는 G의 색도 수는 최소 정수 k이므로 일부 정수 d의 경우 G의 모든 그래프는 (k,d)-색상이 가능하다.예를 들어 모든 평면 그래프는 (4,0)-색상이고 모든 정수 d에 대해 (3,d)-색상이 아닌 평면 그래프가 있기 때문에 평면 그래프 클래스의 색도 수는 4와 같다.

꼭지점 부적정

c를 그래프 G의 꼭지점 색상으로 하자.색상 c에 관한 G의 정점 v의 부적격은 v와 같은 색을 가진 v의 이웃의 수입니다. v의 부적격성이 0이면 v는 적절하게 색칠되었다고 한다.^[1]

정점-색상의 부적합성

c를 그래프 G의 꼭지점 색상으로 하자.c의 부적격은 G의 모든 정점의 부적격의 최대치다.따라서 적절한 정점 색상의 부적합성은 0이다.^[1]

예

5개의 꼭지점에 대한 사이클의 색상 결함의 예인 $C{\displaystyle {}_{}}$ ${\displaystyle {5\mathrm{}}_{}}$ ${\$는 그림에서와 같다$.$첫 번째 하위 수치는 적절한 정점 색상 또는 a (k, 0)-색상의 예다.두 번째 하위 그림은 a(k, 1)-색상의 예이고 세 번째 하위 그림은 a(k, 2)-색상의 예다.참고로,

${\displaystyle \chi _{0}(C_{5})=\chi(C_{5}}=3}$

${\displaystyle \chi _{1}(C_{5})=3}$

$\displaystyle \chi _{2}(C_{n})=1;\forall n\in \mathb {N}}$

특성.

• G의 모든 연결된 구성요소가 (k, d)-색인 경우에만 그래프 G가 (k, d)색인 것처럼 연결된 그래프를 고려해도 충분하다.^[1]
• 그래프 이론적 용어에서, 적절한 정점 색상의 각 색상 등급은 독립적인 집합을 형성하는 반면, 결함 있는 색상의 각 색상 등급은 최대 d의 도에 대한 하위 그래프를 형성한다.^[11]
• 그래프가 (k, d)-색상 가능한 경우, k k k k와 d d d와 같이 각 쌍(k,, d)-)에 대해 색상이 가능하다.^[1]

일부 결과

모든 외부 평면 그래프는 (2,2) 색상이 가능하다.

증명: $G{\displaystyle }$ ${\displaystyle G}$을(를) 연결된 외부 평면 그래프로 표시하십시오$$.Let ${\displaystyle v_{0}}$ be an arbitrary vertex of ${\displaystyle G}$. Let ${\displaystyle V_{i}}$ be the set of vertices of ${\displaystyle G}$ that are at a distance ${\displaystyle i}$ from ${\displaystyle v_{0}}$. Let ${\displaystyle G_{i}}$ be ${\displaystyle ⟨V_i⟩}$${\displaystyle \langle V_{i}\rangele$ $\},$ ${\displaystyle {Vi}_{}}$ ${\$에 의해 유도된 서브그래프$.$ ${\displaystyle {Gi}_{}}${\$displaystyle G_{i}}}}}$이(가) 3 이상의 정점을 포함하고 있다고 가정하면 서브그래프로 K$$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle 3_{}}$ ${\$가 들어 있다.그런 다음 V ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ V ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$. . .${\displaystyle \cup }$ V ${\displaystyle {\mathrm{i}}_{}}$- 1 ${\$의 모든 가장자리를 수축한다.$\cup$ $V\_{\displaystyle {}^{}}$${i-1}$을(를) 새로 얻으려면$$ \cup V ${\displaystyle {\{}^{}}$ ${\$ G$'}.$$⟨{\displaystyle }$ ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ V ${\displaystyle {1\mathrm{}}_{}{}_{}}$ .${\displaystyle \cup }$ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$- ${\displaystyle 1_{}}$ $\langle V_\cup V_{1}\$cup $\$$cup$ ...을 참조하십시오.$\cup V_{i-1}\rangle }$ of ${\displaystyle G'}$ is connected as every vertex in ${\displaystyle V_{i}}$ is adjacent to a vertex in ${\displaystyle V_{i-1}}$. Hence, by contracting all the edges mentioned above, we obtain ${\displaystyle G'}$ such that the subgraph ${\displaystyle ⟨V_0\cup V_1\cup ..}$$.$${\displaystyle \langle V_{0}\컵 V_{1}\cup$$G$cup {\displaystyle $G$$'}$의 \$cup V_{i$}은$($는) ${\displaystyle {Vi}_{}}$ ${\$의 모든 꼭지점에 인접한 단일 꼭지점으로 대체된다$.$따라서 $G{\displaystyle {}^{}}$ $′{\$은(는) $K{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,$$3 {\$displaystyle$ K_${2,3}$를 서브그래프로 포함한다$$$$.그러나 외부 평면 그래프의 모든 하위 그래프는 외부 평면이고 외부 평면 그래프의 가장자리를 수축하여 얻은 모든 그래프는 외부 평면 그래프가 된다.이것은 $K{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle 3_{}}$ ${\$가 모순인 외행성임을$$ 암시한다.따라서 그래프 ${\displaystyle {Gi}_{}}$ ${\$는 3도 이상의 정점을 포함하지 않으며$$, 이는 $G{\displaystyle }$ ${\displaystyle G}$이(가$$) (k, 2) 색상이 가능하다는 것을 의미한다.No vertex of ${\displaystyle V_{i}}$ is adjacent to any vertex of ${\displaystyle V_{i-1}}$ or ${\displaystyle V_{i+1},i\geqslant 1}$, hence the vertices of ${\displaystyle V_{i}}$ can be colored blue if ${\displaystyle i}$ is odd and red if even.따라서 $우리$는 G ${\displaystyle G}$의 (2,2)색상을 생산했다$.$^[1]

코롤러리: 모든 평면 그래프는 색칠이 가능하다.이는 마치 $G{\displaystyle }$ ${\displaystyle G}$이(가) 평면인$$ 경우 모든 ${\displaystyle {Gi}_{}}$ ${\$위의 것과 동일)가 외부 평면인 것처럼 나타난다.따라서 모든 ${\$은(는) 색상이 가능하다$$.따라서 V ${\displaystyle i_{}}$ ${\$의 각 꼭지점은 ${\displaystyle i}$이(가) 짝수일$$ 경우 파란색 또는 빨간색으로, ${\displaystyle i}$이(가) 홀수일$$ 경우 녹색 또는 노란색으로 칠할 수 있으므로$$ $G{\displaystyle }$ ${\displaystystyle G}$의 (4,4) 색상이 생성된다$.$

전체 부차 제외 그래프

모든 정수 $t{\displaystyle }$ ${\displaystyle t}$에 $대해{\displaystyle {}_{}}$ K ${\displaystyle t_{}}$ ${\$ 부차가$$ 없는$$ 모든 그래프 $G{\displaystyle }$ ${\displaystyle G}$은$({\displaystyle t}$-${\displaystyle 1}$, ${\displaystyle N}$) ${\displaystyle (t-1,N)}$ -colourable이$$ 되도록 정수 $N{\displaystyle }$ ${\displaystyty N}$이 있다$$.^[12]

계산 복잡성

결함 있는 색상은 계산적으로 단단하다.$G{\displaystyle }$ ${\displaystyle G}$이(가) 최대 정점 6 또는 최대 정점 7의 평면인 경우에도 지정된 그래프 $G{\displaystyle }$ ${\displaystyle G}$이(가) a(3,1) 색상을 허용하는지를$$ 결정하는 것은 NP 완료다.^[13]

적용들

결함 있는 색상의 적용의 예로는 정점이 작업을 나타내는 스케줄링 문제(컴퓨터 시스템의 사용자라고 함)와 가장자리가 충돌을 나타내는 스케줄링 문제(동일한 파일 중 하나 이상에 액세스해야 함)가 있다.결함을 허용한다는 것은 충돌 임계값을 용인하는 것을 의미한다. 각 사용자는 시스템에서 충돌하는 다른 사용자 두 명과 데이터 검색 시 발생되는 최대 감속을 허용할 수 있으며, 두 명 이상이 허용될 수 없다.^[14]

메모들

참조