Vertex colouring: bounds और exact constructions
उद्देश्य और प्रचलन
Proper vertex colouring जाँचना, मेल खाते lower/upper bounds से chromatic number निकालना, bipartite graphs पहचानना और greedy colouring को optimum से अलग करना सीखें। पूर्वज्ञान: connectivity, cycles, degrees और सामान्य counting। सभी graphs finite, nonempty, simple और undirected हैं। Vertices को colour करते हैं, edges को नहीं। Colour names labels हैं; संख्यात्मक अर्थ केवल उस greedy rule में है जो सबसे छोटा उपलब्ध label चुनती है।
Proper vertex colouring में हर vertex का colour है और adjacent vertices के colours अलग हैं। Nonadjacent vertices colour साझा कर सकते हैं, करना जरूरी नहीं। Graph k-colourable है यदि कोई proper colouring अधिकतम k colours लेती है। Chromatic number χ(G) ऐसा न्यूनतम k है। 4-colouring दिखाने से χ≤4 सिद्ध है, अपने आप χ=4 नहीं।
1. Lower bound और construction से exact उत्तर
Clique ऐसे vertices का set है जिनका हर pair adjacent हो। Size-r clique को r अलग colours चाहिए, इसलिए χ(G)≥r। सबसे बड़े clique का size ω(G) हो तो ω(G)≤χ(G)। Complete graph Kₙ को n colours चाहिए। Nonempty edgeless graph को ठीक 1 चाहिए, isolated vertices कितने भी हों।
Clique lower bound strict हो सकता है। Five-vertex cycle C₅ में edge है लेकिन triangle नहीं, इसलिए ω=2। फिर भी 3 colours चाहिए। Triangle न होने से दो colours पर्याप्त सिद्ध नहीं होते; लंबी odd cycles भी महत्वपूर्ण हैं।
χ(G)=k सिद्ध करने के दो हिस्से हैं: k से कम colours असंभव क्यों, और k colours का वास्तविक valid assignment। 2-colouring की एक असफल कोशिश कुछ सिद्ध नहीं करती, जब तक उससे हर संभव 2-colouring नकार न दी जाए, केवल पहले की खराब choice नहीं।
2. Paths, cycles और parity
कम-से-कम दो vertices के path को 2 colours चाहिए: edge से 1 असंभव, और path पर बारी-बारी दो colours का valid construction है। n≥3 वाले cycle Cₙ का व्यवहार parity पर निर्भर है।
Even cycle में 1,2 बारी-बारी रखें; अंतिम edge भी अलग colours जोड़ती है। इसलिए χ(C₂ₘ)=2। Odd cycle में दो colours बारी-बारी रखने पर अंतिम और पहले vertices समान हो जाते हैं, closing edge गलत होती है। पहली colour चुनने पर हर अगली forced है, इसलिए दूसरी two-colour assignment भी बचा नहीं सकती। तीन पर्याप्त हैं: पहले n−1 vertices पर 1,2 बारी-बारी और अंतिम पर 3। अतः χ(C₂ₘ₊₁)=3।
Exact worked example: rim cycle v1−v2−v3−v4−v5−v1 और extra hub h, जो पाँचों rim vertices से adjacent है। Rim को 3 colours चाहिए। Hub हर rim vertex को छूता है, इसलिए rim की कोई colour नहीं ले सकता; कम-से-कम 4। Rim को 1,2,1,2,3 और hub को 4 दें; valid है, इसलिए χ=4। पूरा edge विवरण wheel graphs के अलग naming conventions से बचाता है।
3. Bipartite graphs और odd cycles
Graph bipartite है यदि vertices को दो independent sets L,R में बाँट सकें और हर edge उनके बीच हो। हर side को एक colour देने से अधिकतम 2 colours की proper colouring मिलती है। कम-से-कम एक edge हो तो ठीक 2 जरूरी; nonempty edgeless graph को केवल 1।
Graph bipartite तभी और केवल तभी है जब odd cycle न हो। आगे की दिशा में हर edge पार करने पर side बदलता है, इसलिए वापस start पर आने के लिए even edges चाहिए।
उलटी दिशा के लिए हर connected component में rooted shortest-path tree चुनें और root से distance की even/odd parity से vertices बाँटें। कोई edge समान parity के vertices जोड़े तो उनके tree paths और वह edge एक odd cycle देंगे; साझा शुरुआती tree path हटा दें। इसलिए odd cycle न होने पर हर edge opposite parities जोड़ती है और bipartition मिलता है। इससे disconnected components को अलग संभालने का कारण भी समझ आता है।
व्यावहारिक two-colour test edges के साथ opposite colours देता है; conflicting edge विफलता बताती है। केवल vertices की even संख्या उपयोगी प्रमाण नहीं: triangle और isolated vertex में कुल चार vertices हैं, फिर भी graph bipartite नहीं।
4. Independent sets से दूसरा lower bound
Independent set के vertices के बीच कोई edge नहीं। Proper colouring की हर colour class independent set है। Maximum independent-set size α(G) और कुल vertices n हों तो k classes अधिकतम kα(G) vertices cover करती हैं। इसलिए χ(G)≥ceil(n/α(G))।
C₅ में α=2: दो nonadjacent vertices चुन सकते हैं, लेकिन five-cycle के कोई भी तीन vertices लें तो उनमें adjacent pair होगा। इसलिए χ≥ceil(5/2)=3, जो explicit 3-colouring से मेल खाता है। यह bound हर graph में equality का theorem नहीं है।
Independent set को matching से न मिलाएँ। Independent set vertices चुनता है; matching common endpoints के बिना edges। Maximum independent set का हर optimum colouring में colour class होना भी जरूरी नहीं। Bound केवल हर class के अधिकतम आकार को सीमित करता है।
5. Greedy colouring और Δ+1 upper bound
दिए vertex order में greedy colouring हर vertex को सबसे छोटी positive colour देती है जो उसके पहले से coloured neighbors ने नहीं ली। Future neighbors अभी coloured नहीं, इसलिए उस step में केवल पिछले neighbors रोकते हैं।
Maximum degree Δ हो तो vertex तक पहुँचने पर अधिकतम Δ अलग colours forbidden हो सकती हैं। Labels 1 से Δ+1 में कम-से-कम एक उपलब्ध होगी। इसलिए हर simple graph में χ(G)≤Δ+1 और greedy उतनी या कम colours की colouring देती है। परिणाम minimum होना जरूरी नहीं।
Worked counterexample: path 1−2−3−4 लें, लेकिन order 1,4,2,3 रखें। Vertex 1 को colour 1; nonadjacent vertex 4 को भी 1। Vertex 2, coloured 1 को छूता है, इसलिए 2 लेता है। Vertex 3 के neighbors 2 और 4 की colours 2 और 1 हैं, इसलिए उसे 3। Greedy ने 3 लिए, जबकि path का असली chromatic number 2 है।
Natural order 1,2,3,4 में greedy colours 1,2,1,2 देती है। Order से algorithm का परिणाम बदलता है, graph का chromatic number नहीं। एक heuristic का परिणाम upper bound है। कुछ orders में सुधार न मिलने से optimum सिद्ध नहीं होता।
6. Disconnected graphs में colours दोबारा लें
G के components G₁,…,G_c हों तो χ(G)=max χ(Gᵢ)। हर component को अपना optimum चाहिए, जिससे lower bound है। Upper bound में हर component उसी maximum-size palette से colour करें; components के बीच edge नहीं, इसलिए palette reuse से conflict नहीं।
C₅ और K₄ components वाले graph का उत्तर max(3,4)=4 है, 3+4=7 नहीं। Disjoint union और सभी cross-edges जोड़कर बने graph अलग constructions हैं; दूसरे में colours reuse रुक सकता है।
ठीक दो named available colours हों तो c connected components वाले bipartite graph के 2^c proper assignments हैं: हर component के two-colour assignment को स्वतंत्र swap कर सकते हैं। Isolated vertex भी दो choices देता है। यह labelled assignments गिनता है, chromatic number नहीं, और दोनों colours का पूरे graph में उपयोग जरूरी नहीं। Odd cycle हो तो केवल इन दो colours के proper assignments 0 हैं।
7. Conflict graph का model
Tasks A,B,C shared resource के कारण अलग time slots में हों, और D केवल C से conflict करे। Tasks vertices और conflicts edges {AB,BC,CA,CD} हों। Time slot colour है। Triangle A,B,C से 3 slots जरूरी; A=1,B=2,C=3,D=1 से 3 पर्याप्त।
केवल बताई constraints model करें। Edge equal colours पर pairwise रोक है; वह task duration, precedence या room capacity नहीं बताती, जब तक प्रश्न दूसरा model न दे। Graph-colouring solution गणितीय रूप से सही हो सकता है, फिर भी अधूरे real scheduling model में महत्वपूर्ण constraints छूट सकती हैं।
जाँच-सूची और आगे का दायरा
Vertices, सारी conflict edges और माँगा परिणाम पहचानें: कोई valid colouring, minimum colours या labelled assignments की संख्या। Exact chromatic number में lower bound और construction साथ दें। केवल triangles नहीं, odd cycles जाँचें। Greedy result upper bound है और disconnected components में colours reuse करें। Chromatic polynomials, edge colouring और उन्नत colouring theorems के लिए अतिरिक्त पाठ चाहिए; यहाँ हर colouring question type पूरा होने का दावा नहीं।
मौलिक अभ्यास: छह single-correct MCQ
मौलिक प्रश्न हैं, पिछले वर्षों के नहीं। हर प्रश्न में ठीक एक विकल्प चुनें। Graphs finite, simple और undirected हैं; दिए matching, labeling और coloring conventions लागू रखें।
C01. Cycle C₅ का chromatic number क्या है?
A. 1 B. 2 C. 5 D. 3
उत्तर: D
A: Edge वाले graph के सभी vertices को एक color नहीं दे सकते।
B: Odd cycle में दो colors alternate करने से अंतिम edge के endpoints same color होंगे।
C: हर vertex का अलग color valid है, लेकिन minimum नहीं।
D: Odd-cycle parity से दो colors असंभव; क्रमशः 1,2,1,2,3 valid three-coloring है।
C02. पाँच-vertex cycle में एक hub जोड़ें जो सभी पाँच cycle vertices से adjacent हो। नए graph का chromatic number क्या है?
A. 3 B. 4 C. 5 D. 6
उत्तर: B
A: Rim को ही तीन colors चाहिए और hub सभी rim vertices से मिलता है, इसलिए कोई rim color नहीं ले सकता।
B: Rim को तीन colors और universal hub को चौथा चाहिए। Rim three-coloring तथा नया hub color से चार मिलते हैं।
C: पाँच आवश्यक नहीं; explicit four-color construction है।
D: छह अलग colors valid पर अनावश्यक हैं और minimum सिद्ध नहीं करते।
C03. Path 1−2−3−4 में order 1,4,2,3 से greedy coloring सबसे छोटा उपलब्ध positive color देती है। वह कितने colors लेती है और χ क्या है?
A. Greedy 2; χ=2 B. Greedy 3; χ=3 C. Greedy 3; χ=2 D. Greedy 4; χ=2
उत्तर: C
A: इस order में 1 और 4 पहले color 1, फिर vertex 2 को 2, इसलिए vertex 3 को 3।
B: Greedy result हमेशा optimal नहीं। Natural order में path की two-coloring है।
C: Processing order में colors 1,1,2,3, लेकिन path पर alternating colors से χ=2।
D: यहाँ किसी step को color 4 नहीं चाहिए; अंतिम vertex colors 1 और 2 देखता है और 3 लेता है।
C04. Bipartite graph में एक तीन-vertex path और दो isolated vertices हैं। दो labeled colors से कितनी proper colorings हैं? हर component में दोनों colors इस्तेमाल करना आवश्यक नहीं।
A. 8 B. 2 C. 4 D. 16
उत्तर: A
A: तीन connected components हैं। Path के दो orientations और हर isolated vertex के स्वतंत्र दो choices: 2³=8।
B: यह केवल path के दो orientations गिनता है, isolated vertices के choices नहीं।
C: यह दोनों के बजाय केवल एक isolated vertex का independent choice गिनता है।
D: तीन independent component choices हैं, चार नहीं; connected path में पहला color चुनने के बाद बाकी forced।
C05. Graph, C₅ और K₄ का disjoint union है। उसका chromatic number क्या है?
A. 7 B. 3 C. 2 D. 4
उत्तर: D
A: Components के बीच edge नहीं, इसलिए colors reuse कर सकते हैं; chromatic numbers जोड़ते नहीं।
B: K₄ के चारों vertices mutually adjacent हैं और चार अलग colors चाहिए।
C: Odd cycle और four-clique दोनों two colors को असंभव बनाते हैं।
D: Component lower bounds से कम-से-कम max(3,4)=4; दोनों में वही four-color palette reuse करके चार पाते हैं।
C06. हर finite simple undirected graph के लिए कौन-सा कथन सही है?
A. Triangle-free से हमेशा bipartite। B. Bipartite होना और odd cycle न होना equivalent हैं। C. Even संख्या में vertices से bipartite। D. Chromatic number हमेशा clique number के बराबर।
उत्तर: B
A: C₅ triangle-free है, लेकिन odd cycle रखता है और bipartite नहीं।
B: Bipartite cycle sides alternate करती है, इसलिए length even। उलटे, odd cycle न होने पर हर component में root-distance parity consistent two-part assignment देती है।
C: Triangle तथा isolated vertex में चार vertices, फिर भी two-coloring नहीं।
D: C₅ का clique number 2 और chromatic number 3, इसलिए सामान्य relation केवल ω≤χ।
स्रोत और दायरा
यह मौलिक पाठ आधिकारिक GATE 2027 CS syllabus के Section 1 के Discrete Mathematics में matching/colouring भाग विकसित करता है। Syllabus से प्रासंगिकता तय होती है, पूरे subject में mastery का दावा नहीं। MIT स्रोत graph definitions और theorems का संदर्भ हैं; यहाँ examples, व्याख्या और अभ्यास मौलिक हैं। बाकी गहराई पाठ में स्पष्ट है, पूरी मान नहीं ली गई।
स्रोत खोले और जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन