임계 그래프

Critical graph
프로젝트 관리의 중요 경로 방법과 혼동하지 마십시오.
왼쪽 상단에서 색도 번호 6의 꼭지점 임계 그래프, 다음으로 색도 번호 5의 모든 N-1 하위 그래프.

그래프 이론에서 임계 그래프는 모든 꼭지점이나 가장자리가 임계 요소인 그래프 G, 즉 그 삭제로 G의 색수가 감소하는 경우 입니다.그러한 감소는 1보다 클 수 없다.

변형

k-임계 그래프(k-critical graph)는 색수 k를 갖는 임계 그래프이며, 색수 k를 갖는 그래프 G는 각각의 정점이 임계 요소인 경우 k-vertex-critical이다.임계 그래프는 색수 측면에서 최소 구성원으로 그래프 이론에서 매우 중요한 척도다.

정점이 n개이고 가장자리가 m인 k-임계 그래프 G의 일부 속성:

  • G는 한 가지 요소만 가지고 있다.
  • G는 유한하다(De Bruijn-Erdős 1951의 De Bruijn-Erdős 정리).
  • Δ(G) ∆ k - 1 즉, 모든 꼭지점이 최소 k - 1 다른 정점에 인접해 있다.더 강하게, G는 (k - 1) 에지로 연결되어 있다.로바스 (1992년) 참조
  • G가 (k - 1)-규칙적인 경우, 즉 모든 정점이 정확히 k - 1 다른 정점에 인접해 있는 경우, G는k K 또는 홀수 사이클이다.이것은 브룩스의 정리다; 브룩스(1941)를 참조하라.
  • 2m ≥ (k - 1) n + k - 3 (Dirac 1957)
  • 2 m ≥ (k - 1) n + [(k - 3)/(k2 - 3)] n (갈라이 1963a)
  • G는 두 개의 서브그래프 각각에서 하나의 꼭지점을 포함하는 모든 꼭지점 쌍 사이의 가장자리가 있는 두 개의 작은 임계 그래프로 분해되거나, G는 적어도 2k - 1정점(갈라이 1963b)을 가질 수 있다.보다 강력한 것은, G가 이러한 유형의 분해를 가지고 있거나, G의 모든 정점 v에 대해, v가 그 색상의 유일한 정점이고, 다른 모든 색상 등급은 적어도 두 개의 정점(Stehlik 2003)을 갖는 k-색상이 있다는 것이다.

그래프 G는 모든 꼭지점 v에 대해 v가 싱글톤 색상 등급인 최적의 적절한 색상이 있는 경우에만 정점에 중요하다.

하조스(1961)가 보여주었듯이, 모든 k-임계 그래프는 완전한 그래프 K에서k 두 개의 비인접 정점을 식별하는 연산을 결합하여 형성될 수 있다.이런 방식으로 형성된 그래프는 항상 적절한 색상에 k 색상을 요구한다.

이중 임계 그래프는 인접한 정점 쌍을 삭제하면 색수가 2만큼 감소하는 연결된 그래프다.한 가지 개방적인 문제는 K가k 유일하게 이중 임계 k-색깔 그래프인지를 판별하는 것이다.[1]

참고 항목

참조

  1. ^ Erd 1967s 1967.

원천

  • Brooks, R. L. (1941), "On colouring the nodes of a network", Proceedings of the Cambridge Philosophical Society, 37 (2): 194–197, doi:10.1017/S030500410002168X
  • de Bruijn, N. G.; Erdős, P. (1951), "A colour problem for infinite graphs and a problem in the theory of relations", Nederl. Akad. Wetensch. Proc. Ser. A, 54: 371–373, doi:10.1016/S1385-7258(51)50053-7. (인덱스). 수학. 13.)
  • Dirac, G. A. (1957), "A theorem of R. L. Brooks and a conjecture of H. Hadwiger", Proceedings of the London Mathematical Society, 7 (1): 161–195, doi:10.1112/plms/s3-7.1.161
  • Erdős, Paul (1967), "Problem 2", In Theory of Graphs, Proc. Colloq., Tihany, p. 361
  • Gallai, T. (1963a), "Kritische Graphen I", Publ. Math. Inst. Hungar. Acad. Sci., 8: 165–192
  • Gallai, T. (1963b), "Kritische Graphen II", Publ. Math. Inst. Hungar. Acad. Sci., 8: 373–395
  • Hajós, G. (1961), "Über eine Konstruktion nicht n-färbbarer Graphen", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 10: 116–117.
  • Jensen, T. R.; Toft, B. (1995), Graph coloring problems, New York: Wiley-Interscience, ISBN 0-471-02865-7
  • Stehlík, Matěj (2003), "Critical graphs with connected complements", Journal of Combinatorial Theory, Series B, 89 (2): 189–194, doi:10.1016/S0095-8956(03)00069-8, MR 2017723.
  • Lovász, László (1992), "Solution to Exercise 9.21", Combinatorial Problems and Exercises (Second Edition), North-Holland
  • Stiebitz, Michael; Tuza, Zsolt; Voigt, Margit (6 August 2009), "On list critical graphs", Discrete Mathematics, Elsevier, 309 (15): 4931–4941, doi:10.1016/j.disc.2008.05.021