Über eine von H. S. WILF angegebene Schranke für die chromatische Zahl endlicher Graphen
✍ Scribed by H.-J. Finck; H. Sachs
- Publisher
- John Wiley and Sons
- Year
- 1969
- Tongue
- English
- Weight
- 651 KB
- Volume
- 39
- Category
- Article
- ISSN
- 0025-584X
No coin nor oath required. For personal study only.
✦ Synopsis
Wir betrachten im folgenden ausschlieljlich ungerichtete nicht-leere endliche Graphen G ohne Schlingen und Mehrfachkanteii. Die n Knotenpunkte von G werden mit P , Q , P*, Pz., . . . bezeichnet. ( P , Q ) ist die P mit Q verbindende Kante, k ( G ) ist die Anzahl der in G enthaltenen Kanten. G' C G bedeutet: G' ist Untergraph von G. Ein maximaler zusammen- liangender Untergraph von G heiljt Komponmt, vcn G. Das Kompbement G von G ist derjenige Graph mit den gleichen Knotenpunkten wie G, in dem zwei verschiedene Knotenpunkte genau d a m durch eine Kante verbunden sind, weiin sie in G nicht verbunden sind. = :n\ ist der vollstkndige Graph rnit n Knotenpunkten, in dem je zwei vcrschiedene Knotenpunkte durch eine Kante verbunden sind. Der Grad r ( Y ; G ) eines Knotenpunktes P bezuglich des Graphen G ist die Anzahl der Kanten von G, mit denen P E G inzidiert. C -P (mit P E G) ist derjenige Graph, welcher aus G entsteht, wenn P und alle mit P inzidenteii Kanten aus G entfernt werden. Eine Farbung der Knotenpunkte von G mit ic Farben heiljt zulussig, wenn je zwei durch eine Karite verbundene Knotenpunkte verschiedene Farben haben. Die chromatische %ahZ x (G) jst die kleinste Bnzahl von E'arben, mit denen die Knotenpunkte von G zulassig gefarbt werden kiinnen. G heiljt kritisch 2) (beziiglich der chromatischen Zahl), wenn x(G') < x ( G ) fur jedeii echten Untergraphen G C G, und G heifit puizkt-krilisch, wenn x ( G -P) < x ( C ) fur jeden Knotenpunkt P E G. #Jeder kritische Graph ist punkt-kritisch ; jeder Graph mit miiidestens einer Kante besitzt einen nichtleeren kritischen Untergraphen mit der gleichen chromatischen Zahl. Ein Graph, der in der Ebene ohne Gberschneidung von Kanten gezeichnet werden kann, heiljt planar. G + 1) Untersuchungen iiber kritische Graphen finden sich insbesondere bei DIRAC [3]-[6] und GALLAI [9, 101.