이퀄리티 컬러링

수학의 영역인 그래프 이론에서, 공평한 색채는 다음과 같은 방식으로 무방향 그래프의 정점에 색을 할당하는 것입니다.

인접한 두 정점의 색상이 동일하지 않습니다.
두 가지 색상 클래스의 정점 수는 최대 1개까지 다릅니다.

즉, 다른 색상의 정점 분할은 가능한 한 균일합니다.예를 들어, 각 정점에 고유한 색상을 부여하는 것은 공평하지만, 일반적으로 최적의 균등 색상에 필요한 것보다 훨씬 많은 색상을 사용합니다.등가 색채를 정의하는 동등한 방법은 동일한 정점을 가진 Turan 그래프의 하위 그래프로서 주어진 그래프를 포함시키는 것이다.균등한 ^[1]색채와 관련된 두 가지 종류의 색채가 있습니다.그래프 G의 등가색 k는 G가 k색의 등가색 k가 되도록 가장 작은 수이다.그러나 G는 더 많은 수의 색에 대해 균등하게 색을 칠하지 않을 수 있습니다. G의 균등 색역치는 ^[2]k보다 크거나 같은 수의 색에 대해 균등하게 색을 칠할 수 있도록 가장 작은 k입니다.

Paul Erd)s(1964년)에 의해 추측으로 제시되고 Andras Hajnal과 Endre Szemerédi(1970년)에 의해 증명된 Hajnal-Szemerédi 정리는 최대 차수의 그래프는 δ + 1 색상의 균등한 색상을 갖는다고 명시한다.몇 가지 관련 추측이 아직 미해결인 채로 있다.다항식 시간 알고리즘은 또한 이 ^[3]경계에 일치하는 색을 찾는 것과 특별한 종류의 그래프에 대한 최적의 색을 찾는 것으로 알려져 있지만, 임의의 그래프가 주어진 수의 색을 갖는 등가색인지 아닌지를 결정하는 보다 일반적인 문제는 NP-완전이다.

예

스타K의_1,5 균등한 색채입니다.

그림에 표시된 별_1,5 K는 완전한 초당 그래프이므로 두 가지 색으로 색칠할 수 있습니다.그러나 결과 색상은 하나의 색 클래스에 하나의 정점이 있고 다른 색 클래스에 5개가 있으므로 동등하지 않습니다.이 그래프의 등가색상의 최소 색수는 그림과 같이 4가지입니다.다른 색 클래스가 모두 최대 2개의 정점을 가지려면 중앙 정점이 해당 색 클래스의 유일한 정점이어야 합니다.따라서 다른 5개의 정점은 최소 3개의 색 클래스로 분할되어야 합니다.보다 일반적으로 Meyer(1973)는 모든 별 K에_1,n 1 $\scriptstyle 1+\lceil n/2\rceil$ + $\scriptstyle 1+\lceil n/2\rceil$ 2 $\scriptstyle 1+\lceil n/2\rceil$ δ $\$ 1 $+\lceil$ n/ $2\rceil }$ 의 $\scriptstyle 1+\lceil n/2\rceil$ 색이 어떠한 등가색에도 $\scriptstyle 1+\lceil n/2\rceil$ 을 관찰한다.따라서 그래프의 색수는 n/4의 배수로 등가 될 수 있다.K는 최대 5도를 가지기 때문에_1,5, 하지날-제메레디 정리에 의해 보장되는 색의 수는 6이며, 각 정점에 구별되는 색을 부여함으로써 달성된다.

또 다른 흥미로운 현상은 다른 완전 이분 그래프인_{2n + 1,2n + 1} K에 의해 나타난다.이 그래프는 양분화를 통해 얻을 수 있는 공평한 2색입니다.단, 균등 (2n + 1)-색상은 없습니다.많은 색 클래스로 나누어진 정점의 균등한 분할은 클래스당 정확히 2개의 정점을 가져야 합니다.다만, 양쪽에 홀수수의 정점이 있기 때문에, 각각 쌍으로 분할할 수 없습니다.따라서 이 그래프의 균등 색역치는 2n + 2로 균등 색수 2보다 훨씬 크다.

하지날 스제메레디 정리

Brooks의 정리는 최대 차수가 δ인 연결된 그래프는 두 가지 예외(완전 그래프 및 홀수 주기)를 제외하고 δ-색상을 갖는다고 말합니다.그러나 이 색상은 일반적으로 균일하지 않을 수 있습니다.Paul Erd's(1964)는 한 가지 색상만 더 있어도 균등하게 색을 칠 수 있다고 추측했다. 즉, 최대 차수의 모든 그래프는 δ + 1 색상의 균등하게 색을 칠할 수 있다.사례 δ = 2는 간단하며(경로와 주기의 조합은 3가지 색상의 반복 패턴을 사용하여 균등하게 색칠할 수 있으며, 주기를 닫을 때 반복에 대해 약간의 조정을 가함) 사례 δ + 1 = n/3은 이전에 Corradi & Hajnal에 의해 해결되었다.완전한 추측은 Hajnal & Szemerédi(1970)에 의해 증명되었고, 현재는 Hajnal-Szemerédi 정리라고 알려져 있다.그들의 원래 증거는 길고 복잡했다. 더 간단한 증거는 Kierstead & Kostochka(2008)에 의해 제시되었다.이렇게 많은 색상으로 균일한 색을 찾는 다항식 시간 알고리즘은 Kierstead와 Kostochka에 의해 설명되었습니다.그들은 Marcelo Mydlarz와 Endre Szemerédi를 이전의 미공개 다항식 시간 알고리즘으로 간주합니다.키에르스테드와 코스토치카는 또한 모든 인접한 두 정점이 최대 2k + 1에 도를 더하는 것을 가질 때마다 균등한 k-색채가 존재한다는 것을 보여주기 위해 정리의 강화를 증명하지는 않는다.

마이어(1973)는 브룩스의 균등색정리의 한 형태를 추측했다: 최대도 δ를 갖는 모든 연결된 그래프는 완전한 그래프와 홀수 주기를 제외하고 δ 이하의 색을 갖는 균등색이다.이 추측의 강화된 버전은 이러한 그래프 각각이 정확히 δ색을 갖는 균등한 색채를 가지며, 한 가지 추가 예외는 초당파의 양쪽이 동일한 홀수 개의 ^[1]정점을 갖는 완전한 초당 그래프를 갖는다는 것이다.

시모어(1974)는 밀도 그래프가 해밀턴이라는 디락의 정리를 가정하는 하지날-스제메레디 정리의 강화를 제안했다. 그는 n-vertex 그래프의 모든 정점이 k단계에서 가장 멀리 떨어져 있는 정점을 연결함으로써 형성된 그래프를 하위 그래프로 포함한다고 추측했다.n 사이클케이스 k = 1은 디락의 정리 그 자체이다.Hajnal-Szemerédi 정리는 주어진 그래프의 보완 그래프에 k의 큰 값에 대한 추측을 적용하고, n 사이클에서 정점의 연속적인 연속성을 색상 클래스로 사용함으로써 이 추측으로부터 회복할 수 있다.시모어의 추측은 대략적으로 증명되었다. 즉, 모든 정점이 최소 kn/(k ^[4]+ 1)+o(n)개의 인접점을 갖는 그래프에 대해.그 증명은 하즈날-스제메레디 정리 자체를 포함한 몇 가지 깊은 도구를 사용한다.

하즈날-스제메레디 정리의 또 다른 일반화로는 볼로바시-엘드리지-카틀린 추측(또는 ^[5]줄여서 BEC-공제)이 있다.이것은 G와₂ G가 각각 최대도 δ와₁ δ를₂ 갖는 n개의 정점에 대한 그래프이고₁ (δ₁ + 1)(δ₂ + 1) ≤ n+1이면 G와₁₂ G를 채울 수 있음을 나타낸다.즉₁, G와₂ G는 공통의 모서리가 없는 n개의 정점 집합에서 나타낼 수 있습니다.Hajnal-Szemerédi 정리는 G가₂ 집단들의 분리된 결합인 이 추측의 특별한 경우이다.Catlin(1974)은 δ₁ 및 δ에₂ 대해 이와 유사하지만 강력한 조건을 제공하여 이러한 패킹이 존재함을 보증합니다.

그래프의 특수 클래스

최대 차수 δ인 모든 나무의 경우, 균등 색수는 최대

(\displaystyle 1+\lceil\Delta/2\rceil})

^[6]

별에 대한 최악의 경우입니다.그러나 대부분의 나무는 상당히 작은 균등 색수를 가지고 있다: n개의 정점이 있는 나무가 δ n/3 - O(1)를 가지고 있다면, 그것은 오직 3가지 ^[7]색상으로 균등 색채를 가진다.Furmacczyk(2006)는 그래프 제품의 균등한 색수를 연구한다.

계산의 복잡성

가능한 한 적은 색상으로 균등한 색을 찾는 문제(하즈날-제메레디 경계 이하)도 연구되었다.그래프 착색에서 균등 색상으로의 간단한 감소는 그래프에 충분히 많은 고립된 정점을 추가함으로써 증명될 수 있으며, 그래프가 주어진 수의 색상으로 균등 색소를 가지는지 여부를 테스트하는 것이 NP-완전임을 보여준다.그러나 특수 등급의 그래프로 제한되거나 매개 변수화된 복잡성의 관점에서 문제가 더 흥미로워진다.Bodlaender&Fomin(2005년)여부 G시간에 O(nO( 아는 일))공정한 c-coloring을 인정하는 G의 어디에선은 treewidth는, 그래프 G와 색깔의 번호 c를 고려하면 그것은 실험하는 것. 특히, 공평한 채색을 최적으로 나무를 위해 다항 시간(이전에 첸 및 때문에, Lih 1994년 알려진)과outerplanar gra으로 해결할 것도 가능할 것이다 보여 주었다.phs.다항식 시간 알고리즘은 분할 그래프의 ^[8]균등하게 색칠하는 것으로도 알려져 있다.단, 펠로우 등 (2007)는 트리 너비가 알고리즘의 파라미터일 때 문제가 W[1]-hard임을 증명한다.따라서 이 파라미터와 무관한 다항식 시간 알고리즘이 존재할 가능성이 낮거나 실행시간 공식에서 파라미터에 대한 의존성이 지수에서 벗어날 수 있습니다.

적용들

Meyer(1973)가 제안한 균등한 색채에 대한 한 가지 동기는 일정 문제에 관한 것이다.이 응용 프로그램에서 그래프의 정점은 수행해야 할 태스크의 집합을 나타내며, 엣지는 동시에 수행해서는 안 되는 두 태스크를 연결합니다.이 그래프의 색상은 동시에 수행할 수 있는 하위 집합으로 작업의 파티션을 나타냅니다. 따라서 색상의 색 수는 전체 작업을 수행하는 데 필요한 시간 단계 수에 해당합니다.로드밸런싱을 고려하기 위해 각 시간 스텝에서 동일한 수 또는 거의 동일한 수의 작업을 수행하는 것이 바람직하며, 이 균형은 균등한 색상으로 실현됩니다.Furmacczyk(2006)는 이러한 유형의 스케줄링 문제의 특정 응용을 언급하고 있으며, 이용 가능한 타임슬롯 간에 코스가 균등하게 분산되어 서로 호환되지 않는 코스의 페어를 동시에 스케줄 하는 것을 회피하는 방법으로 대학 코스를 타임슬롯에 할당하고 있습니다.

하지날-제메레디 정리는 의존성이 제한된 랜덤 변수의 합계의 분산을 제한하기 위해 사용되었다(Pemmaraju 2001; Janson & Ruciiski 2002).(LovaaSz 국소 보조법 설정처럼) 각 변수가 최대 Ω의 다른 변수에 의존하는 경우, 의존성 그래프의 균등한 색상을 사용하여 변수를 체르노프 경계가 계산될 수 있는 독립 하위 집합으로 분할할 수 있으며, 따라서 분할이 non-eq에서 수행된 경우보다 분산에 대한 전체 경계가 더 엄격해질 수 있다.uatable한 방법.

메모들

^ ^a ^b Furmacczyk (2006)
^ k가 그래프 내의 꼭지점 수보다 클 경우 모든 색 클래스가 0 또는 하나의 꼭지점을 갖는 k 색상의 균등한 색상이 존재하므로 모든 그래프에는 균등한 색상의 임계값이 있습니다.
^ Kierstead, Henry A.; Kostochka, Alexandr V.; Mydlarz, Marcelo; Szemerédi, Endre (2010-09-17). "A fast algorithm for equitable coloring". Combinatorica. 30 (2): 217–224. CiteSeerX 10.1.1.224.5588. doi:10.1007/s00493-010-2483-5. ISSN 0209-9683.
^ Komlos, Sarközy & Szemerédi(1998).
^ 볼로바스와 엘드리지(1978년).
^ 마이어(1973년).
^ Bodlaender & Guy (1983) harvts 오류: 대상 없음: CITREF Bodlaender Guy1983 (도움말)
^ Chen, Ko & Lih(1996년).

레퍼런스

를 클릭합니다Bodlaender, Hans L.; Fomin, Fedor V. (2005), "Equitable colorings of bounded treewidth graphs", Theoretical Computer Science, 349 (1): 22–30, doi:10.1016/j.tcs.2005.09.027, MR 2183465.
를 클릭합니다Bollobás, B.; Eldridge, S. E. (1978), "Packings of graphs and applications to computational complexity", Journal of Combinatorial Theory, Series B, 25 (2): 105–124, doi:10.1016/0097-3165(78)90073-0, MR 0511983.
를 클릭합니다Bollobás, Béla; Guy, Richard K. (1983), "Equitable and proportional coloring of trees", Journal of Combinatorial Theory, Series B, 34 (2): 177–186, doi:10.1016/0095-8956(83)90017-5, MR 0703602.
Catlin, Paul A. (1974), "Subgraphs of graphs. I.", Discrete Mathematics, 10 (2): 225–233, doi:10.1016/0012-365X(74)90119-8, MR 0357230
를 클릭합니다Chen, Bor-Liang; Lih, Ko-Wei (1994), "Equitable coloring of trees", Journal of Combinatorial Theory, Series B, 61 (1): 83–87, doi:10.1006/jctb.1994.1032, MR 1275266.
Chen, Bor-Liang; Ko, Ming-Tat; Lih, Ko-Wei (1996), "Equitable and m-bounded coloring of split graphs", Combinatorics and Computer Science (Brest, 1995), Lecture Notes in Computer Science, vol. 1120, Berlin: Springer-Verlag, pp. 1–5, doi:10.1007/3-540-61576-8_67, ISBN 978-3-540-61576-7, MR 1448914
를 클릭합니다Corrádi, K.; Hajnal, A. (1963), "On the maximal number of independent circuits in a graph", Acta Mathematica Academiae Scientiarum Hungaricae, 14 (3–4): 423–439, doi:10.1007/BF01895727, MR 0200185.
를 클릭합니다Erdős, Paul (1964), "Problem 9", in Fieldler, M. (ed.), Theory of Graphs and its Applications, Prague: Czech Acad. Sci. Publ., p. 159.
Fellows, 마이클 Fomin, 표도르 V;Lokshtanov, 다니엘;Rosamond, 프랜시스, Saurabh, 사켓;Szeider, 스테판,.Thomassen, 카르스텐(2007년),"어떤 다채로운 문제의 복잡성 treewidth에 의해 parameterized일", 조합 최적화 및 응용 프로그램(PDF), 강의 노트 컴퓨터 과학으로, 4616 vol., 베를린:Springer-Verlag,를 대신하여 서명함. 366–377, doi:10.1007/978-3-540-73556-4_38, 아이 에스비엔 978-3-540-73555-7, MR2397574.
를 클릭합니다Furmańczyk, Hanna (2006), "Equitable coloring of graph products" (PDF), Opuscula Mathematica, 26 (1): 31–44, MR 2272280.
를 클릭합니다Hajnal, A.; Szemerédi, E. (1970), "Proof of a conjecture of P. Erdős", Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), North-Holland, pp. 601–623, MR 0297607.
를 클릭합니다Janson, Svante; Ruciński, Andrzej (2002), "The infamous upper tail", Random Structures & Algorithms, 20 (3): 317–342, doi:10.1002/rsa.10031, MR 1900611.
Kierstead, H. A.; Kostochka, A. V. (2008), "A short proof of the Hajnal-Szemerédi theorem on equitable colouring", Combinatorics, Probability and Computing, 17 (2): 265–270, doi:10.1017/S0963548307008619, MR 2396352
를 클릭합니다Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre (1998), "Proof of the Seymour conjecture for large graphs", Annals of Combinatorics, 2 (1): 43–60, CiteSeerX 10.1.1.122.2352, doi:10.1007/BF01626028, MR 1682919.
를 클릭합니다Meyer, Walter (1973), "Equitable coloring", American Mathematical Monthly, 80 (8): 920–922, doi:10.2307/2319405, JSTOR 2319405.
를 클릭합니다Pemmaraju, Sriram V. (2001), "Equitable colorings extend Chernoff-Hoeffding bounds", Proc. 12th ACM-SIAM Symp. Discrete Algorithms (SODA 2001), Soda '01, pp. 924–925, ISBN 9780898714906.
를 클릭합니다Seymour, P. (1974), "Problem section", in McDonough, T. P.; Mavron, Eds., V. C. (eds.), Combinatorics: Proceedings of the British Combinatorial Conference 1973, Cambridge, UK: Cambridge Univ. Press, pp. 201–202.

외부 링크

ECPT A 브런치 및 컷알고리즘에 의한 등색 문제 해결

[F06-1] Furmacczyk (2006)

[2] 가 그래프 내의 꼭지점 수보다 클 경우 모든 색 클래스가 0 또는 하나의 꼭지점을 갖는 k 색상의 균등한 색상이 존재하므로 모든 그래프에는 균등한 색상의 임계값이 있습니다.

[3] Kierstead, Henry A.; Kostochka, Alexandr V.; Mydlarz, Marcelo; Szemerédi, Endre (2010-09-17). "A fast algorithm for equitable coloring". Combinatorica. 30 (2): 217–224. CiteSeerX 10.1.1.224.5588. doi:10.1007/s00493-010-2483-5. ISSN 0209-9683.

[4] Komlos, Sarközy & Szemerédi(1998).

[5] 볼로바스와 엘드리지(1978년).

[6] 마이어(1973년).

[7] Bodlaender & Guy (1983) harvts 오류: 대상 없음: CITREF Bodlaender Guy1983 (도움말)

[8] Chen, Ko & Lih(1996년).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Search