리스트 컬러링

List coloring

수학의 한 분야인 그래프 이론에서 목록 색상은 각 꼭지점이 허용되는 색상 목록으로 제한될 수 있는 그래프 색상의 한 유형이다.1970년대에 비징과 에르드제스, 루빈, 테일러에 의해 독립 논문에서 처음 연구되었다.[1]

정의

그래프 G가 주어지고 각 꼭지점 v(목록이라고 함)에 대해 설정된 L(v)의 색상이 주어지면 목록 색상은 모든 꼭지점 v를 목록 L(v)의 색상에 매핑하는 선택함수다.그래프 색상과 마찬가지로 리스트 색상은 일반적으로 적절한 것으로 가정되며, 이는 인접한 두 정점이 동일한 색상을 받지 못한다는 것을 의미한다.그래프는 각 꼭지점에 k 색상의 목록을 어떻게 할당하든 적절한 목록 색상이 있는 경우 k-선택 가능(또는 k-list-colorable)이다.그래프 G의 선택성(또는 리스트 색도 또는 리스트 색도 번호) ch(G)는 G가 k-선택 가능한 최소 숫자 k이다.

보다 일반적으로, 각 꼭지점 v에 양의 정수 f(v)를 할당하는 함수의 경우, 그래프 G는 각 꼭지점 v에 f(v) 색상 목록을 할당하는 방법과 상관없이 목록 색상이 있으면 f-선택 가능(또는 f-list-list-colorable)이다.특히 모든 정점 v에 = k 이면 f-chelectsability는 k-chelectsability에 해당한다.

예

A와 B가 W, X, Y, Z의 모든 W, X, Y, Z에 각각 연결되고 다른 정점이 연결되지 않는 정점 A, B, W, X, Y, Z의 정점 6개를 갖는 완전한2,4 초당적 그래프 G = K를 고려한다.초당적 그래프로서 G는 통상적인 색수 2를 가지고 있다: 하나는 A와 B를 한 색으로, 다른 하나는 W, X, Y, Z를 다른 색으로 칠할 수 있으며, 두 개의 인접한 정점들은 동일한 색상을 가지지 않을 것이다.반면, 다음 구성에서 알 수 있듯이 G는 목록 색채 숫자가 2보다 크며, 목록 색채 수는 A와 B에 할당한다: {red, blue} 및 {green, black}.나머지 4개의 꼭지점에 목록 {red, green}, {red, black}, {blue, green}, {blue, black}을(를) 할당하십시오.A 리스트의 색상과 B 리스트의 색 중 어떤 것을 선택하든, 이미 두 가지 선택이 이웃을 색칠하는 데 쓰일 정도로 다른 꼭지점이 있을 것이다.따라서 G는 2차 선택이 불가능하다.

반면, G는 3-선택이 가능하다는 것을 쉽게 알 수 있다: 정점 A와 B에 임의의 색을 선택하면 나머지 정점 각각에 대해 적어도 하나의 사용 가능한 색상이 남고, 이러한 색상은 임의로 선택할 수 있다.

정점당 세 가지 색상으로 구성된 전체 초당 그래프K의3,27 목록 색상 인스턴스.중앙 정점 3개에 대해 어떤 색상을 선택하든 외부 27 정점 중 하나는 수리할 수 없어 K의3,27 목록 색수가 최소 4개임을 보여준다.

보다 일반적으로 q를 양의 정수로 하고, G를 완전한 양분 그래프 K로q,qq 한다.사용 가능한 색상은 q의2 서로 다른 두 자리 숫자로 나타내도록 한다.초당파의 한 쪽에는 q 꼭지점에 {i0, i1, i2, ...의 색상 세트를 부여한다.첫 번째 숫자 i의 가능한 q 선택 각각에 대해 첫 번째 숫자가 서로 동일한 }.초당파의 반대편에서 qq 정점에 {0a, 1b, 2c, ...의 색상 세트를 부여한다.} q-투플(a, b, c, ...)의 가능한 각 q-투플q(q-tuple) 선택 항목에 대해 첫 번째 숫자가 모두 구별되는 경우.이 그림에는 q = 3으로 구성된 동일한 구조의 더 큰 예가 나와 있다.

그러면 G는 L에 대한 목록 색상을 가지고 있지 않다: 양분 작은 쪽의 정점에 대해 어떤 색상을 선택하든, 이 선택은 양분 반대편의 정점에 대한 모든 색상과 충돌할 것이다.예를 들어 색상이 {00,01}인 정점이 01이고 색상이 {10,11}인 정점이 10인 경우 색상이 {01,10}인 정점은 색상을 지정할 수 없다.따라서 G의 목록 색소수는 최소한 q + 1이다.[2]

마찬가지로, =( - ){\인 경우, 완전한 초당적 그래프n, n K는 k-선택할 수 없다.예를 들어, 2k - 1 색상은 총체적으로 사용할 수 있고, 양분 단면에서 각 정점은 이러한 색상의 k-tuple을 서로 다른 정점들과 사용할 수 있다고 가정하자.그리고 나서, 초당파의 각 면은 적어도 k 색상을 사용해야 한다. 모든 k - 1 색상은 하나의 꼭지점 목록에서 분리되기 때문이다.한쪽에는 적어도 k 색상이 사용되고 다른 한쪽에는 k 색상이 사용되므로 양쪽에는 한 가지 색상이 사용되어야 하지만 이는 인접한 두 꼭지점의 색상이 동일하다는 것을 의미한다.특히 효용 그래프 K는3,3 목록-색깔 번호가 3개 이상이고, 그래프10,10 K는 목록-색깔 번호가 4개 이상이다.[3]

특성.

그래프 G의 경우 χ(G)는 색도 수를 나타내고 Δ(G)는 G의 최대 정도를 나타내도록 한다.목록 색상 번호 ch(G)는 다음과 같은 특성을 만족한다.

  1. ch(G) ≥(G).k-list-colorable 그래프는 특히 모든 꼭지점에 k-coloring에 해당하는 동일한 k-color 색상이 할당될 때 목록 색상이 있어야 한다.
  2. ch(G)는 일반적으로 색수 측면에서 경계할 수 없으며, 즉 ch(G) ≤ f(χ)가 모든 그래프 G에 대해 잡는 함수 f가 없다.특히 전체 초당파 그래프 예에서 알 수 있듯이 χ(G) = 2가 되되 ch(G)가 임의로 큰 그래프가 존재한다.[2]
  3. ch(G) ≤(G) ln(n) 여기서 n은 G의 정점 수입니다.[4][5]
  4. ch(G) Δ(G)[3][6] + 1
  5. ch(G) ≤ G가 평면 그래프인 경우 5.[7]
  6. ch(G) ≤ G가 초당적 평면 그래프인 경우 ≤ 3.[8]

컴퓨팅 선택성 및 (a, b) 선택성

문헌에서 두 가지 알고리즘 문제가 고려되었다.

  1. k-선택성: 주어진 k에 대해 k-선택 가능한지 여부를 결정하고,
  2. (a, b)-선택 가능성: 주어진 함수 에 대해 주어진 그래프를 f-선택할 수 있는지 결정→ { …,

초당적 그래프의 k-선택성은 완료되며, 평면 그래프에서는 4-선택성, 평면 삼각형이 없는 그래프에서는 3-선택성, 초당적 평면 그래프에서는 (2)-선택성에도 동일하게 적용된다.[9][10]P-프리5 그래프의 경우, 즉 5-Vertex 경로 그래프를 제외한 그래프의 경우 k-chossability는 고정-모수 추적이 가능하다.[11]

그래프의 2코어에 도달할 때까지 도 0의 정점이나 1의 정점을 반복적으로 삭제하여 선형 시간에 2 선택 가능한지 여부를 테스트할 수 있으며, 이후에는 더 이상 그러한 삭제가 불가능하다.초기 그래프는 2-코어가 짝수 사이클이거나 2-길이의 2개 경로와 3-길이의 3개 경로로 구성된 세타 그래프일 경우에만 선택할 수 있다.[3]

적용들

목록 색상은 채널/주파수 할당과 관련된 실제적인 문제에서 발생한다.[12][13]

참고 항목

참조

  1. ^ Jensen, Tommy R.; Toft, Bjarne (1995), "1.9 List coloring", Graph coloring problems, New York: Wiley-Interscience, pp. 18–21, ISBN 0-471-02865-7
  2. ^ a b Gravier, Sylvain (1996), "A Hajós-like theorem for list coloring", Discrete Mathematics, 152 (1–3): 299–302, doi:10.1016/0012-365X(95)00350-6, MR 1388650.
  3. ^ a b c Erdős, P.; Rubin, A. L.; Taylor, H. (1979), "Choosability in graphs", Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata (PDF), Congressus Numerantium, vol. 26, pp. 125–157, archived from the original (PDF) on 2016-03-09, retrieved 2008-11-10
  4. ^ Eaton, Nancy (2003), "On two short proofs about list coloring - Part 1" (PDF), Talk, archived from the original (PDF) on August 29, 2017, retrieved May 29, 2010
  5. ^ Eaton, Nancy (2003), "On two short proofs about list coloring - Part 2" (PDF), Talk, archived from the original (PDF) on August 30, 2017, retrieved May 29, 2010
  6. ^ Vizing, V. G. (1976), "Vertex colorings with given colors", Metody Diskret. Analiz. (in Russian), 29: 3–10
  7. ^ Thomassen, Carsten (1994), "Every planar graph is 5-choosable", Journal of Combinatorial Theory, Series B, 62: 180–181, doi:10.1006/jctb.1994.1062
  8. ^ Alon, Noga; Tarsi, Michael (1992), "Colorings and orientations of graphs", Combinatorica, 12 (2): 125–134, doi:10.1007/BF01204715
  9. ^ Gutner, Shai (1996), "The complexity of planar graph choosability", Discrete Mathematics, 159 (1): 119–130, arXiv:0802.2668, doi:10.1016/0012-365X(95)00104-5.
  10. ^ Gutner, Shai; Tarsi, Michael (2009), "Some results on (a:b)-choosability", Discrete Mathematics, 309 (8): 2260–2270, doi:10.1016/j.disc.2008.04.061
  11. ^ Heggernes, Pinar; Golovach, Petr (2009), "Choosability of P5-free graphs" (PDF), Mathematical Foundations of Computer Science, Lecture Notes on Computer Science, vol. 5734, Springer-Verlag, pp. 382–391
  12. ^ Wang, Wei; Liu, Xin (2005), "List-coloring based channel allocation for open-spectrum wireless networks", 2005 IEEE 62nd Vehicular Technology Conference (VTC 2005-Fall), vol. 1, pp. 690–694, doi:10.1109/VETECF.2005.1558001.
  13. ^ Garg, N.; Papatriantafilou, M.; Tsigas, P. (1996), "Distributed list coloring: how to dynamically allocate frequencies to mobile base stations", Eighth IEEE Symposium on Parallel and Distributed Processing, pp. 18–25, doi:10.1109/SPDP.1996.570312, hdl:21.11116/0000-0001-1AE6-F.

추가 읽기

  • Aigner, Martin; Ziegler, Günter (2009), Proofs from THE BOOK (4th ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-642-00855-9, 34장 5색 평면 그래프.
  • 디에스텔, 라인하드.그래프 이론. 2005년 스프링거 3판.5.4장 착색 목록.다운로드 가능한 전자판