Zuckerman, David Linear degree extractors and the inapproximability of Max Clique and Chromatic Number. (English) Zbl 1301.68152 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 681-690 (2006). MSC: 68Q17 05C15 05C69 11B75 68Q25 PDFBibTeX XMLCite \textit{D. Zuckerman}, in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 681--690 (2006; Zbl 1301.68152) Full Text: DOI
Montassier, Mickaël; Raspaud, André A note on 2-facial coloring of plane graphs. (English) Zbl 1178.05042 Inf. Process. Lett. 98, No. 6, 235-241 (2006). MSC: 05C15 68R10 PDFBibTeX XMLCite \textit{M. Montassier} and \textit{A. Raspaud}, Inf. Process. Lett. 98, No. 6, 235--241 (2006; Zbl 1178.05042) Full Text: DOI
Skulrattanakulchai, San \(\Delta \)-list vertex coloring in linear time. (English) Zbl 1178.05044 Inf. Process. Lett. 98, No. 3, 101-106 (2006). MSC: 05C15 05C85 68Q25 PDFBibTeX XMLCite \textit{S. Skulrattanakulchai}, Inf. Process. Lett. 98, No. 3, 101--106 (2006; Zbl 1178.05044) Full Text: DOI
Bucko, Jozef; Mihók, Peter On uniquely partitionable relational structures and object systems. (English) Zbl 1142.05024 Discuss. Math., Graph Theory 26, No. 2, 281-289 (2006). MSC: 05C15 05C20 05C65 05C75 PDFBibTeX XMLCite \textit{J. Bucko} and \textit{P. Mihók}, Discuss. Math., Graph Theory 26, No. 2, 281--289 (2006; Zbl 1142.05024) Full Text: DOI
Gera, Ralucca; Zhang, Ping On stratification and domination in graphs. (English) Zbl 1142.05026 Discuss. Math., Graph Theory 26, No. 2, 249-272 (2006). MSC: 05C15 05C69 PDFBibTeX XMLCite \textit{R. Gera} and \textit{P. Zhang}, Discuss. Math., Graph Theory 26, No. 2, 249--272 (2006; Zbl 1142.05026) Full Text: DOI Link
Zuo, Liancui; Yu, Qinglin; Wu, Jianliang Tree coloring of distance graphs with a real interval set. (English) Zbl 1137.05313 Appl. Math. Lett. 19, No. 12, 1341-1344 (2006). MSC: 05C15 05C12 PDFBibTeX XMLCite \textit{L. Zuo} et al., Appl. Math. Lett. 19, No. 12, 1341--1344 (2006; Zbl 1137.05313) Full Text: DOI
Li, Jingwen; Zhang, Donghan On the vertex-distinguishing edge coloring of \(S_n \vee K_{n,n}\). (English) Zbl 1131.05040 Int. J. Pure Appl. Math. 31, No. 3, 361-364 (2006). MSC: 05C15 PDFBibTeX XMLCite \textit{J. Li} and \textit{D. Zhang}, Int. J. Pure Appl. Math. 31, No. 3, 361--364 (2006; Zbl 1131.05040)
Zuo, Liancui; Wu, Jianliang; Liu, Jiazhuang The vertex linear arboricity of the integer distance graph \(G(D_{m,k,2})\). (Chinese. English summary) Zbl 1127.05032 J. Syst. Sci. Math. Sci. 26, No. 5, 522-532 (2006). Reviewer: Hang Lau (Montréal) MSC: 05C12 PDFBibTeX XMLCite \textit{L. Zuo} et al., J. Syst. Sci. Math. Sci. 26, No. 5, 522--532 (2006; Zbl 1127.05032)
Marciniszyn, Martin; Skokan, Jozef; Spöhel, Reto; Steger, Angelika Threshold functions for asymmetric Ramsey properties involving cliques. (English) Zbl 1155.05332 Díaz, Josep (ed.) et al., Approximation, randomization and combinatorial optimization. Algorithms and techniques. 9th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2006, and 10th international workshop on randomization and computation, RANDOM 2006, Barcelona, Spain, August 28–30, 2006. Proceedings. Berlin: Springer (ISBN 3-540-38044-2/pbk). Lecture Notes in Computer Science 4110, 462-474 (2006). MSC: 05C55 05C15 05C69 05C85 PDFBibTeX XMLCite \textit{M. Marciniszyn} et al., Lect. Notes Comput. Sci. 4110, 462--474 (2006; Zbl 1155.05332) Full Text: DOI Link
Radcliffe, Mary; Zhang, Ping On irregular colorings of graphs. (English) Zbl 1124.05035 AKCE Int. J. Graphs Comb. 3, No. 2, 175-191 (2006). Reviewer: Lorenzo Traldi (Easton) MSC: 05C15 PDFBibTeX XMLCite \textit{M. Radcliffe} and \textit{P. Zhang}, AKCE Int. J. Graphs Comb. 3, No. 2, 175--191 (2006; Zbl 1124.05035)
Liu, Jingfa; Huang, Wenqi The vertex strong total chromatic number of the general graph \(K(n,m)\). (Chinese. English summary) Zbl 1126.05049 Pure Appl. Math. 22, No. 2, 159-162, 209 (2006). Reviewer: Le Maohua (Zhanjiang) MSC: 05C15 PDFBibTeX XMLCite \textit{J. Liu} and \textit{W. Huang}, Pure Appl. Math. 22, No. 2, 159--162, 209 (2006; Zbl 1126.05049)
Schiermeyer, Ingo Upper bounds for the chromatic number of a graph. (English) Zbl 1134.05315 Faigle, U. (ed.) et al., CTW2006. Cologne-Twente Workshop on graphs and combinatorial optimization, Lambrecht, Germany, June 5–9, 2006. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 25, 147-148 (2006). MSC: 05C15 PDFBibTeX XMLCite \textit{I. Schiermeyer}, Electron. Notes Discrete Math. 25, 147--148 (2006; Zbl 1134.05315) Full Text: DOI
Bujtás, Csilla; Tuza, Zsolt Mixed colorings of hypergraphs. (English) Zbl 1202.05042 Meszka, Mariusz (ed.), Fifth Cracow conference on graph theory, USTRON ’06, Ustroń, Poland, September 11–15, 2006. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 24, 273-275 (2006). MSC: 05C15 05C65 PDFBibTeX XMLCite \textit{C. Bujtás} and \textit{Z. Tuza}, Electron. Notes Discrete Math. 24, 273--275 (2006; Zbl 1202.05042) Full Text: DOI
Rabern, Landon On graph associations. (English) Zbl 1188.05068 SIAM J. Discrete Math. 20, No. 2, 529-535 (2006). MSC: 05C15 05C69 PDFBibTeX XMLCite \textit{L. Rabern}, SIAM J. Discrete Math. 20, No. 2, 529--535 (2006; Zbl 1188.05068) Full Text: DOI arXiv Link
Rodríguez, J. A.; Sigarreta, J. M. Offensive alliances in cubic graphs. (English) Zbl 1116.05060 Int. Math. Forum 1, No. 33-36, 1773-1782 (2006). Reviewer: Ioan Tomescu (Bucureşti) MSC: 05C69 05C15 PDFBibTeX XMLCite \textit{J. A. Rodríguez} and \textit{J. M. Sigarreta}, Int. Math. Forum 1, No. 33--36, 1773--1782 (2006; Zbl 1116.05060) Full Text: DOI arXiv
Gera, Ralucca; Rasmussen, Craig; Horton, Steve Dominator colorings and safe clique partitions. (English) Zbl 1113.05032 Congr. Numerantium 181, 19-32 (2006). MSC: 05C15 05C69 PDFBibTeX XMLCite \textit{R. Gera} et al., Congr. Numerantium 181, 19--32 (2006; Zbl 1113.05032)
Zuo, Lian-Cui; Wu, Jian-Liang; Liu, Jia-Zhuang The vertex linear arboricity of an integer distance graph with a special distance set. (English) Zbl 1141.05034 Ars Comb. 79, 65-76 (2006). Reviewer: Tomáš Kaiser (Plzeň) MSC: 05C70 05C38 11B75 05C12 PDFBibTeX XMLCite \textit{L.-C. Zuo} et al., Ars Comb. 79, 65--76 (2006; Zbl 1141.05034)
Adiga, Chandrashekar; Zaferani, R. Kafshgar On colorings of strongly multiplicative and strongly quotient graphs. (English) Zbl 1109.05093 Adv. Stud. Contemp. Math., Kyungshang 13, No. 2, 171-182 (2006). MSC: 05C78 05C15 05C69 PDFBibTeX XMLCite \textit{C. Adiga} and \textit{R. K. Zaferani}, Adv. Stud. Contemp. Math., Kyungshang 13, No. 2, 171--182 (2006; Zbl 1109.05093)
Jungić, Veselin; Král’, Daniel; Škrekovski, Riste Colorings of planar graphs with no rainbow faces. (English) Zbl 1174.05364 Combinatorica 26, No. 2, 169-182 (2006). MSC: 05C15 PDFBibTeX XMLCite \textit{V. Jungić} et al., Combinatorica 26, No. 2, 169--182 (2006; Zbl 1174.05364) Full Text: DOI
Albertson, Michael O.; Mohar, Bojan Coloring vertices and faces of locally planar graphs. (English) Zbl 1106.05038 Graphs Comb. 22, No. 3, 289-295 (2006). MSC: 05C15 05C10 PDFBibTeX XMLCite \textit{M. O. Albertson} and \textit{B. Mohar}, Graphs Comb. 22, No. 3, 289--295 (2006; Zbl 1106.05038) Full Text: DOI
Jendrol’, Stanislav Rainbowness of cubic plane graphs. (English) Zbl 1109.05044 Discrete Math. 306, No. 24, 3321-3326 (2006). Reviewer: Van Bang Le (Rostock) MSC: 05C15 52B10 PDFBibTeX XMLCite \textit{S. Jendrol'}, Discrete Math. 306, No. 24, 3321--3326 (2006; Zbl 1109.05044) Full Text: DOI
Naserasr, Reza \(K_{5}\)-free bound for the class of planar graphs. (English) Zbl 1111.05039 Eur. J. Comb. 27, No. 7, 1155-1158 (2006). Reviewer: Gerd Wegner (Dortmund) MSC: 05C15 PDFBibTeX XMLCite \textit{R. Naserasr}, Eur. J. Comb. 27, No. 7, 1155--1158 (2006; Zbl 1111.05039) Full Text: DOI
Sebő, András A Berge-keeping operation for graphs. (English) Zbl 1102.05028 Discrete Math. 306, No. 19-20, 2582-2592 (2006). MSC: 05C17 05C15 05C69 PDFBibTeX XMLCite \textit{A. Sebő}, Discrete Math. 306, No. 19--20, 2582--2592 (2006; Zbl 1102.05028) Full Text: DOI
Valencia-Pabon, Mario; Vera, Juan Independence and coloring properties of direct products of some vertex-transitive graphs. (English) Zbl 1111.05040 Discrete Math. 306, No. 18, 2275-2281 (2006). Reviewer: Saul Stahl (Lawrence) MSC: 05C15 05C69 PDFBibTeX XMLCite \textit{M. Valencia-Pabon} and \textit{J. Vera}, Discrete Math. 306, No. 18, 2275--2281 (2006; Zbl 1111.05040) Full Text: DOI
Kostyuk, Victor; Narayan, Darren A.; Williams, Victoria A. Minimal rankings and the arank number of a path. (English) Zbl 1101.05040 Discrete Math. 306, No. 16, 1991-1996 (2006). Reviewer: Haiko Müller (Leeds) MSC: 05C35 05C15 05C38 05C78 PDFBibTeX XMLCite \textit{V. Kostyuk} et al., Discrete Math. 306, No. 16, 1991--1996 (2006; Zbl 1101.05040) Full Text: DOI
Borowiecki, Mieczysław; Jendrol’, Stanislav; Král’, Daniel; Miškuf, Jozef List coloring of Cartesian products of graphs. (English) Zbl 1100.05033 Discrete Math. 306, No. 16, 1955-1958 (2006). Reviewer: Van Bang Le (Rostock) MSC: 05C15 PDFBibTeX XMLCite \textit{M. Borowiecki} et al., Discrete Math. 306, No. 16, 1955--1958 (2006; Zbl 1100.05033) Full Text: DOI
Luo, Rong; Zhao, Yue A note on Vizing’s independence number conjecture of edge chromatic critical graphs. (English) Zbl 1112.05039 Discrete Math. 306, No. 15, 1788-1790 (2006). Reviewer: Gabriel Semanišin (Košice) MSC: 05C15 05C69 PDFBibTeX XMLCite \textit{R. Luo} and \textit{Y. Zhao}, Discrete Math. 306, No. 15, 1788--1790 (2006; Zbl 1112.05039) Full Text: DOI
Axenovich, Maria On subgraphs induced by transversals in vertex-partitions of graphs. (English) Zbl 1097.05018 Electron. J. Comb. 13, No. 1, Research paper R36, 11 p. (2006). MSC: 05C15 PDFBibTeX XMLCite \textit{M. Axenovich}, Electron. J. Comb. 13, No. 1, Research paper R36, 11 p. (2006; Zbl 1097.05018) Full Text: EuDML EMIS
Li, Xiang-Yang; Wang, Yu Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks. (English) Zbl 1096.68784 J. Parallel Distrib. Comput. 66, No. 4, 515-530 (2006). MSC: 68W25 68M10 68R10 PDFBibTeX XMLCite \textit{X.-Y. Li} and \textit{Y. Wang}, J. Parallel Distrib. Comput. 66, No. 4, 515--530 (2006; Zbl 1096.68784) Full Text: DOI
Teguia, Alberto M.; Godbole, Anant P. Sierpiński gasket graphs and some of their properties. (English) Zbl 1095.05038 Australas. J. Comb. 35, 181-192 (2006). MSC: 05C99 05C38 05C45 05C69 05C15 PDFBibTeX XMLCite \textit{A. M. Teguia} and \textit{A. P. Godbole}, Australas. J. Comb. 35, 181--192 (2006; Zbl 1095.05038) Full Text: arXiv
Mahmoodian, E. S.; Omoomi, Behnaz; Peng, Y. H. On the defining sets of some special graphs. (English) Zbl 1100.05036 Australas. J. Comb. 35, 69-81 (2006). Reviewer: Van Bang Le (Rostock) MSC: 05C15 PDFBibTeX XMLCite \textit{E. S. Mahmoodian} et al., Australas. J. Comb. 35, 69--81 (2006; Zbl 1100.05036)
Qiu, Pengxiang; Zhang, Zhongfu; Bian, Liang; Qiang, Huiying; Chao, Fugang On the vertex-distinguishing edge coloring of join graph with star and complete balanced bipartite graph. (English) Zbl 1098.05503 Int. J. Pure Appl. Math. 27, No. 2, 255-262 (2006). Reviewer: Van Bang Le (Rostock) MSC: 05C15 68R10 94C15 PDFBibTeX XMLCite \textit{P. Qiu} et al., Int. J. Pure Appl. Math. 27, No. 2, 255--262 (2006; Zbl 1098.05503)
Schwarz, Christopher; Troxell, Denise Sakai \(L(2,1)\)-labelings of Cartesian products of two cycles. (English) Zbl 1089.05065 Discrete Appl. Math. 154, No. 10, 1522-1540 (2006). MSC: 05C78 05C15 05C50 05C90 94A05 PDFBibTeX XMLCite \textit{C. Schwarz} and \textit{D. S. Troxell}, Discrete Appl. Math. 154, No. 10, 1522--1540 (2006; Zbl 1089.05065) Full Text: DOI
Coja-Oghlan, Amin; Moore, Cristopher; Sanwalani, Vishal MAX \(k\)-CUT and approximating the chromatic number of random graphs. (English) Zbl 1094.68118 Random Struct. Algorithms 28, No. 3, 289-322 (2006). MSC: 68W25 05C85 05C15 05C80 68R10 90C22 05C07 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} et al., Random Struct. Algorithms 28, No. 3, 289--322 (2006; Zbl 1094.68118) Full Text: DOI
Zverovich, Igor E. A new kind of graph coloring. (English) Zbl 1090.05031 J. Algorithms 58, No. 2, 118-133 (2006). Reviewer: Gerd Wegner (Dortmund) MSC: 05C15 68R10 68Q17 PDFBibTeX XMLCite \textit{I. E. Zverovich}, J. Algorithms 58, No. 2, 118--133 (2006; Zbl 1090.05031) Full Text: DOI
Murat, Cécile; Paschos, Vangelis Th. On the probabilistic minimum coloring and minimum \(k\)-coloring. (English) Zbl 1087.05025 Discrete Appl. Math. 154, No. 3, 564-586 (2006). Reviewer: Ove Frank (Stockholm) MSC: 05C15 05C80 90B15 68R10 68W25 PDFBibTeX XMLCite \textit{C. Murat} and \textit{V. Th. Paschos}, Discrete Appl. Math. 154, No. 3, 564--586 (2006; Zbl 1087.05025) Full Text: DOI
Cornaz, Denis; Fonlupt, Jean Chromatic characterization of biclique covers. (English) Zbl 1087.05043 Discrete Math. 306, No. 5, 495-507 (2006). Reviewer: Haiko Müller (Leeds) MSC: 05C69 05C15 05C70 05C85 68R10 90C05 90C10 90C27 PDFBibTeX XMLCite \textit{D. Cornaz} and \textit{J. Fonlupt}, Discrete Math. 306, No. 5, 495--507 (2006; Zbl 1087.05043) Full Text: DOI
Żyliński, Paweł Orthogonal art galleries with holes: a coloring proof of Aggarwal’s theorem. (English) Zbl 1087.05020 Electron. J. Comb. 13, No. 1, Research paper R20, 10 p. (2006). MSC: 05C15 05C90 PDFBibTeX XMLCite \textit{P. Żyliński}, Electron. J. Comb. 13, No. 1, Research paper R20, 10 p. (2006; Zbl 1087.05020) Full Text: EuDML EMIS
Linial, Nathan; Saks, Michael; Statter, David The non-crossing graph. (English) Zbl 1081.05027 Electron. J. Comb. 13, No. 1, Research paper N2, 8 p. (2006). MSC: 05C10 05C69 05C15 PDFBibTeX XMLCite \textit{N. Linial} et al., Electron. J. Comb. 13, No. 1, Research paper N2, 8 p. (2006; Zbl 1081.05027) Full Text: EuDML EMIS