서브컬러링

네 가지 색상으로 구성된 최적되지 않은 하위 색상.빨간색과 파란색, 그리고 녹색과 노란색을 합치면 단 두 가지 색상으로만 서브 컬러링이 만들어진다.

그래프 이론에서 하위 색상은 그래프 정점에 색상을 할당하여 각 색 등급이 정점 부조화를 유도하는 것이다.즉, 각 색상 등급은 군집 그래프를 구성해야 한다.

그래프 G의 하위 색수 χ_S(G)는 G의 하위 색상에 필요한 가장 적은 색이다.

서브컬러링과 서브크롬 번호는 알버트슨 외 연구진(1989)에 의해 도입되었다.

그래프의 모든 적절한 컬러링과 코콜로링도 하위 컬러링이기 때문에 어떤 그래프의 서브 컬러링 수는 기껏해야 색수와 동일한 색채 번호와 같다.

서브컬러링은 (컬러링과 마찬가지로) NP완료라는 점에서 컬러링만큼 정확히 해결하기 어렵다.구체적으로는 평면 그래프의 색소수가 최대 2인 경우인지 여부를 결정하는 문제는 NP-완전하다.

• 최대 4도의 삼각형이 없는 그래프(Gimbel & Hartman 2003)(Fiala et al. 2003),
• 최대 등급 4의 비교가능성 그래프(Ochem 2017),
• 최대 4도의 초당적 그래프를 나타내는 선 그래프(Gonsalves & Ochem 2009),
• 둘레 5의 그래프(Montassier & Ochem 2015).

cograph의 하위 색소수는 다항 시간(Fiala et al. 2003)으로 계산할 수 있다.모든 고정 정수 r에 대해, 다항 시간 내에 간격의 하위 색상과 순열 그래프가 최대 r인지 여부를 결정할 수 있다(Broersma et al. 2002).

참조

• Albertson, M. O.; Jamison, R. E.; Hedetniemi, S. T.; Locke, S. C. (1989), "The subchromatic number of a graph", Discrete Mathematics, 74 (1–2): 33–49, doi:10.1016/0012-365X(89)90196-9.
• Broersma, Hajo; Fomin, Fedor V.; Nesetril, Jaroslav; Woeginger, Gerhard (2002), "More About Subcolorings", Computing, 69 (3): 187–203, doi:10.1007/s00607-002-1461-1.
• Fiala, J.; Klaus, J.; Le, V. B.; Seidel, E. (2003), "Graph Subcolorings: Complexity and Algorithms", SIAM Journal on Discrete Mathematics, 16 (4): 635–650, CiteSeerX 10.1.1.3.183, doi:10.1137/S0895480101395245.
• Gimbel, John; Hartman, Chris (2003), "Subcolorings and the subchromatic number of a graph", Discrete Mathematics, 272 (2–3): 139–154, doi:10.1016/S0012-365X(03)00177-8.
• Gonçalves, Daniel; Ochem, Pascal (2009), "On star and caterpillar arboricity", Discrete Mathematics, 309 (11): 3694–3702, doi:10.1016/j.disc.2008.01.041.
• Montassier, Mickael; Ochem, Pascal (2015), "Near-Colorings: Non-Colorable Graphs and NP-Completeness", Electronic Journal of Combinatorics, 22 (1): #P1.57.
• Ochem, Pascal (2017), "2-subcoloring is NP-complete for planar comparability graphs", Information Processing Letters, 128: 46–48, arXiv:1702.01283, doi:10.1016/j.ipl.2017.08.004.