벡터 색도 수가 색도 보다 작은 작은 그래프 를 찾고 있습니다.
Gχv(G)<χ(G)
( 가있는 경우 는 벡터 색수 . 여기서 인접 정점과 연관된 벡터는 직관적으로 멀리 떨어져 있습니다. 요구 사항은 예를 들어, 의 경우 삼각형의 정점이 충분합니다.)
Gq
x:V→Rd
⟨x(v),x(w)⟩≤−1/(q−1)
q=3
그래프의 벡터 색도는 색도 수보다 크지 않습니다 : . 예는 인 그래프로 알려져 있습니다. (Karger, Motwani, 수단의 원본 논문 [JACM, 45 : 246-265] ( manuscript )은 일반화 된 Kneser 그래프를 제안하며, 최신 논문은 임의 단위 벡터를 기반으로 한 구성을 사용합니다.)
χv(G)≤χ(G)χv(G)=3
χ(G)=nδ
내가 예를 생각 그래프 와 및 (컴퓨터 계산에 기초하여). 이 그래프에는 20 개의 정점과 90 개의 모서리가 있습니다.
Kχv(K)=4
χ(K)=8
더 작은 예가 있습니까? 유혹의 길은 그러한 짐승이 존재한다면 Chvatal 또는 Grötzsch 그래프의 콘크리트 벡터 3 색을 제공하는 것입니다.
( 는 필요는 없지만 좋을 것입니다. 업데이트 : 아래에서 지적했듯이 비 적분 사례는 실제로 쉽습니다. 감사합니다.)
χv업데이트 : Grötzsch and Chvátal
Chvátal 및 Grötzsch 그래프의 3 색 벡터에 대한 생각에는 저항 할 수 없었습니다.
Grötsch 그래프는 다음과 같이 3 색 벡터가 될 수 있습니다. 북극에 5도 노드를 놓습니다. 5도 -4 노드는 북쪽에서 약 77 도의 동일한 위도에 균등하게 배치됩니다. 지구의 북반구에 그려진 오각형을 상상해보십시오. 남은 반구 (북쪽에서 약 135도)에서 남은 5 개의 노드 (3도)가 끝납니다. 의 경도는 5 명의 경도와 동일합니다. (필요한 경우 도면을 업로드하지만 생각보다 TikZ에서 측지선을 그리는 것이 더 어렵습니다.)
SDP 솔버에 따르면 Chvátal은 벡터 3 색도 인정하지만 출력은 5 차원의 벡터 묶음으로 해석하기가 어렵습니다.
(3 번째 시도 실패 : Yury의 구조에서 영감을 얻은 후 5 사이클을 가져와 다른 모든 꼭지점에 꼭지점을 추가합니다.이 그래프의 색도는 4입니다. 그러나 솔버에 따르면 벡터는 3 색이 아닙니다.)
답변
나는 내 의견에 답을한다. 가 필요가없는 경우 가장 작은 예는 5 개의 정점에 대한주기)입니다.
G = C 5 χ v ( C 5 ) = √
G=C5
이 예제를 가 정수인 예제로 변환하는 것은 어렵지 않습니다 . 하자 두 5 사이클 조합 될 과 로부터의 각 정점에 의 각 꼭지점에 연결되어 . 이라고하자 . 마지막으로 는 과 의 합집합입니다 . 그런 다음
G1
C5(1)
C5(2)
C5(1)
C5(2)
G2=K5
G
G1
G2
답변
여기에 단위 구에 Grötzsch 그래프가 포함됩니다. 
이것은 명백한 방식으로 벡터 채색에 해당합니다. 예를 들어, 북극의 정점은 벡터 (0,0,1)로 채색됩니다.
Grötsch 그래프에는 3 가지 유형의 노드가 있습니다. 단일 정도 5 노드 (북쪽). 5도 4 노드 (북반구, N에 등거리, 3 개를 만들 수 있음). 5도 3 노드 (남반구에서 N과 같은 거리에 3 개를 만들 수 있음).
N은 남반구의 5 개의 이웃과 녹색 가장자리로 연결되어 있습니다. (녹색 가장자리는 북반구의 4도 각도에서 발생하는 것처럼 보이지만 임베딩의 인공물입니다.)
정상에서 본, 당신의 내장 로바 츠와 유사한 정도 4 개 노드 '에 의해 기술 된 오각형 밖으로 만들 수 평면에를 :
C5
마지막으로 남극 위에서 본 모습 : 
내 계산을 믿으려면 모든 인접한 정점이 서로 120도 이상이므로 유효한 벡터 3 색을 구성합니다. Grötzsch 그래프는 4 색입니다. 11 개의 정점, 20 개의 모서리 벡터 채색은 3 차원으로되어 있기 때문에이 예제에 특히 만족합니다. KMS 그래프 색상 알고리즘을 설명하기 위해 임의의 초평면을 그립니다.