Bojenje grafa (cvorova)

Jel ima neko neki (pametan) rad ili pak zna neki algoritam o bojenju cvorova grafa? Neku pametnu heuristiku ili slicno...

---

A kako konkretno glasi problem?

Ja sam radio jedan zadatak sa bojenjem grafa u samo 2 boje.
Trebalo je obojiti u crno tako da nema dva susedna crna cvora (maximalno bojenje).
Resenje nije nesto pametno.Samo lupas random cvor,skines sve susede i njega, i tako sve dok ne upotrebis sve cvorove...Tako sam nalupao 300 puta ( a moze i manje ) i zadatak je prosao.

Edit:
Mislim, ovo je ako ti treba "AC" :) , a ako ti treba neki pouzdan algoritam , sem backtrackinga, nemam pojma :).

EDIT !
Andreja, nisi u pravu za BFS.
Evo ti jedan test primer
Grane : 1-2,1-3,2-4,2-5,3-4,3-6,4-6,5-6,6-7. ( recimo krenes BFS iz cvora 1 i videces da to ne radi ).

_{[Ovu poruku je menjao Relaja dana 22.10.2006. u 11:04 GMT+1]}

---

Ma to sa dve boje je onda bipartitan graf, nema tu da pustas random cvorove. Pustis BFS svaki drgi nivo bojis crno. Da, inace u opstem grafu bojenje je NP problem... Ja kokretno znam neke heuristike ali me interesuje da li ovo neko DOBRO poznaje.
A problem inace glasi:
Imas graf G (V, E) i treba da napraivis funkciju F:V -> {1,..,k}, tako da je, ukoliko je (u,v) ivica, tada je F(u) != F (v). To je bojenje grafa po cvorovima. Inace ti treba da nadjes funkciju za koju je k najmanje (ti u svakom slucaju mozes svakom cvoru da dodelis drugu boju ali to je onda |V|).

---

Graf mozes da obojis sa dve boje akko je bipartitan. U tvom primeru on moze da se oboji sa tri boje ali nikako sa dve! Imas ciklus neparne duzine: 3-4-6, koji ne mozes da obojis sa dve boje. Razmisli malo!

---

zaboravio sam reci da dve bele mogu biti susedne.

---

The URL for this search is http://xxx.lanl.gov/find/grp_c...D+graph+coloring/0/1/0/all/0/1
Showing results 1 through 15 (of 15 total) for ti:(graph AND coloring)

1. cs.CG/0609033 [abs, ps, pdf, other] :
Title: Choosing Colors for Geometric Graphs via Color Space Embeddings
Authors: Michael B. Dillencourt, David Eppstein, Michael T. Goodrich
Comments: 12 pages, 4 figures. To appear at 14th Int. Symp. Graph Drawing, 2006
Subj-class: Computational Geometry
ACM-class: G.1.6

2. math.CO/0607071 [abs, ps, pdf, other] :
Title: NP-completeness of 4-incidence colorability of semi-cubic graphs
Authors: Xueliang Li, Jianhua Tu
Comments: 11 pages
Subj-class: Combinatorics; Computational Complexity
MSC-class: 05C15; 68Q17

3. cs.DM/0509023 [abs, ps, pdf, other] :
Title: A linear algorithm for coloring vertices of a graph or finding a Meyniel obstruction
Authors: Kathie Cameron (WLU), Jack Edmonds (EP INSTITUTE), Benjamin Lévêque (Leibniz - IMAG), Frédéric Maffray (Leibniz - IMAG)
Subj-class: Discrete Mathematics

4. cs.DM/0504082 [abs, ps, pdf, other] :
Title: Coloring Artemis graphs
Authors: Benjamin Lévêque (Leibniz - IMAG), Frédéric Maffray (Leibniz - IMAG), Bruce Reed, Nicolas Trotignon (Leibniz - IMAG)
Subj-class: Discrete Mathematics
ACM-class: G.2.2

5. cs.AI/0502082 [abs, ps, pdf, other] :
Title: Graphs and colorings for answer set programming
Authors: Kathrin Konczak, Thomas Linke, Torsten Schaub
Subj-class: Artificial Intelligence; Logic in Computer Science

6. cond-mat/0403725 [abs, ps, pdf, other] :
Title: Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
Authors: Florent Krzakala, Andrea Pagnani, Martin Weigt
Comments: 23 pages, 10 figures. Replaced with accepted version
Subj-class: Disordered Systems and Neural Networks; Statistical Mechanics; Computational Complexity
Journal-ref: Phys. Rev. E 70, 046705 (2004)

7. cs.NE/0309039 [abs, ps, pdf, other] :
Title: Two novel evolutionary formulations of the graph coloring problem
Authors: V. C. Barbosa, C. A. G. Assis, J. O. do Nascimento
Comments: To appear in Journal of Combinatorial Optimization
Subj-class: Neural and Evolutionary Computing
ACM-class: F.2.2; I.2.8
Journal-ref: Journal of Combinatorial Optimization 8 (2004), 41-63

8. math.CO/0211317 [abs, ps, pdf] :
Title: On graph coloring check-digit method
Authors: Kamil Kulesza, Zbigniew Kotulski
Comments: 7 pages, paper sumitted to Applied Mathematics Letters (Elsevier)
Subj-class: Combinatorics; Cryptography and Security; Discrete Mathematics; Data Structures and Algorithms
MSC-class: D.4.6; E.4

9. cond-mat/0208460 [abs, ps, pdf, other] :
Title: Coloring random graphs
Authors: R. Mulet, A. Pagnani, M. Weigt, R. Zecchina
Comments: 4 pages, 1 figure, version to app. in PRL
Subj-class: Statistical Mechanics; Disordered Systems and Neural Networks; Computational Complexity
Journal-ref: Phys. Rev. Lett. 89, 268701 (2002)

10. cs.CR/0208007 [abs, ps, pdf] :
Title: On the graph coloring check-digit scheme with applications to verifiable secret sharing
Authors: Kamil Kulesza, Zbigniew Kotulski
Subj-class: Cryptography and Security; Discrete Mathematics; Combinatorics
ACM-class: D.4.6; E.4

11. cs.CC/0106045 [abs, ps, pdf, other] :
Title: A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs
Authors: Andre Grosse, Joerg Rothe, Gerd Wechsung
Comments: 9 pages, appears in part in an ICTCS 2001 paper by the same authors, minor revision of the above
Subj-class: Computational Complexity
ACM-class: F.1.3; F.2.2

12. cs.DS/0105029 [abs, ps, pdf, other] :
Title: Coloring k-colorable graphs using relatively small palettes
Authors: Eran Halperin, Ram Nathaniel, Uri Zwick
Comments: 16 pages, 2 figures. A preliminary version of this paper appeared in the proceedings the of 12th ACM-SIAM Symposium on Discrete Algorithm (SODA'01) under a slightly different title
Subj-class: Data Structures and Algorithms; Computational Complexity; Discrete Mathematics
ACM-class: F.2.2;G.2.2;G.3;G.1.6

13. cs.DS/0011009 [abs, ps, pdf, other] :
Title: Small Maximal Independent Sets and Faster Exact Graph Coloring
Authors: David Eppstein
Comments: 8 pages
Subj-class: Data Structures and Algorithms; Combinatorics
ACM-class: F.2.2
Journal-ref: J. Graph Algorithms & Applications 7(2):131-140, 2003

14. cs.DS/9812008 [abs, ps, pdf, other] :
Title: Approximate Graph Coloring by Semidefinite Programming
Authors: David Karger, Rajeev Motwani, Madhu Sudan
Subj-class: Data Structures and Algorithms
ACM-class: F.2.2;G.2.2;G.3
Journal-ref: JACM 45(2), mar. 1998, pp.246--265

15. cond-mat/9810144 [abs, ps, pdf, other] :
Title: Relaxation in graph coloring and satisfiability problems
Authors: Pontus Svenson, Mats G. Nordahl
Comments: 13 pages, 22 figures. Several changes to text, figures added, section on feromagnetic model moved to a separate publication. Accepted for publication in Phys Rev. E
Subj-class: Disordered Systems and Neural Networks; Artificial Intelligence
Journal-ref: Phys. Rev. E 59(4) 3983-3999 (1999)