0
반음계 숫자가 그래프 (Cliques)의 가장 큰 전체 부분 그래프 크기와 같습니까?
반음계 번호와 cliques 사이에 어떤 관계가 있습니까?그래프 채색 - 채도 숫자
A
답변
0
일반적으로 질문에 대한 답변은 "아니오"입니다. 및 "아니오"
최대 도수가 그 색수와 동일한 그래프를 "완전"이라고합니다. 최근에 풀린 모든 완벽한 그래프를 분류하는 것은 유명한 열린 문제였습니다. 그래프는 Berge 그래프 인 경우에만 완벽합니다.
그래프가 반음계 번호 k를 갖는 경우 반음계 수라고 생각하면 k 개의 꼭지점에 대한 전체 그래프가 미성년자로 표시됩니다. (Hadwiger의 추측)
두 번째 질문에 대해서는 사소한 도발 숫자가 반음계 숫자보다 작거나 같으면 강력한 연결이 없습니다. 삼각형 자유 그래프의 경우 도수, 반음 수 및 최대 차수를 나타내는 여러 가지 추측이 있습니다 (Reed '98 참조)
그건 프로그래밍이 아니라 순수한 수학입니다. http://mathoverflow.net/ 또는 http://math.stackexchange.com/ – NeplatnyUdaj
글쎄, 내가 붙어있는 그래프 착색 문제를 모델링하고있다. 저는 단지 가치 영역을 이해할 수있는 두 가지 힌트를 가지고 있습니다. – kuz
색도> = | C |. – Ante