LEADER 05300nam 2200649 450 001 9910141196003321 005 20170815153913.0 010 $a1-283-33198-5 010 $a9786613331984 010 $a1-118-03249-7 010 $a1-118-03074-5 035 $a(CKB)2670000000133154 035 $a(EBL)695948 035 $a(OCoLC)768230300 035 $a(SSID)ssj0000554814 035 $a(PQKBManifestationID)11356212 035 $a(PQKBTitleCode)TC0000554814 035 $a(PQKBWorkID)10517363 035 $a(PQKB)10010730 035 $a(MiAaPQ)EBC695948 035 $a(EXLCZ)992670000000133154 100 $a20160816h19951995 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aGraph coloring problems /$fTommy R. Jensen, Bjarne Toft 210 1$aNew York, New York :$cJohn Wiley & Sons, Inc.,$d1995. 210 4$dİ1995 215 $a1 online resource (324 p.) 225 1 $aWiley-Interscience Series in Discrete Mathematics and Optimization 300 $a"A Wiley-Interscience Publication." 311 $a0-471-02865-7 320 $aIncludes bibliographical references at the end of each chapters and indexes. 327 $aGraph Coloring Problems; Contents; Preface; 1 Introduction to Graph Coloring; 1.1 Basic Definitions; 1.2 Graphs on Surfaces; 1.3 Vertex Degrees and Colorings; 1.4 Criticality and Complexity; 16.14 Partition Problem of Galvin and Hajnal; 1.5 Sparse Graphs and Random Graphs; 1.6 Perfect Graphs; 1.7 Edge-Coloring; 1.8 Orientations and Integer Flows; 1.9 List Coloring; 1.10 Generalized Graph Coloring; 1.11 Final Remarks; Bibliography; 2 Planar Graphs; 2.1 Four-Color Theorem; 2.2 Cartesian Sequences; 2.3 Intersection Graphs of Planar Segments; 2.4 Ringerl's Earth-Moon Problem 327 $a2.5 Ore and Plummer's Cyclic Chromatic Number2.6 Vertex Partitionings w.r.t. Coloring Number; 2.7 Vertex Partitionings w.r.t. Maximum Degree; 2.8 The Three-Color Problem; 2.9 Steinberg's Three-Color Problem; 2.10 Gru?nbaum and Havel's Three-Color Problem; 2.11 Gro?tzsch and Sachs' Three-Color Problem; 2.12 Barnette's Conjecture; 2.13 List-Coloring Planar Graphs; 2.14 Kronk and Mitchem's Entire Chromatic Number; 2.15 Nine-Color Conjecture; 2.16 Uniquely Colorable Graphs; 2.17 Density of 4-Critical Planar Graphs; 2.18 Square of Planar Graphs; Bibliography; 3 Graphs on Higher Surfaces 327 $a3.1 Heawood's Empire Problem3.2 Gru?nbaum's 3-Edge-Color Conjecture; 3.3 Albertson's Four-Color Problem; 3.4 Improper Colorings; 3.5 Number of 6-Critical Graphs on a Surface; 3.6 Toroidal Polyhedra; 3.7 Polynomial Coloring of Embedded Graphs; 3.8 Sparse Embedded Graphs; 3.9 Ringel's 1-Chromatic Number; 3.10 Borodin's Conjecture on Diagonal Coloring; 3.11 Acyclic Colorings; 3.12 Cochromatic Numbers; 3.13 Graphs on Pseudo-Surfaces; Bibliography; 4 Degrees; 4.1 The Coloring Number; 4.2 Coloring of Decomposable Graphs; 4.3 Color-Bound Families of Graphs; 4.4 Edge-Disjoint Placements 327 $a4.5 Powers of Hamilton Cycles4.6 Brooks' Theorem for Triangle-Free Graphs; 4.7 Graphs Without Large Complete Subgraphs; 4.8 k-Chromatic Graphs of Maximum Degree k; 4.9 Total Coloring; 4.10 Equitable Coloring; 4.11 Acyclic Coloring; 4.12 Melnikov's Valency-Variety Problem; 4.13 Induced-Odd Degree Subgraphs; 4.14 Strong Chromatic Number; Bibliography; 5 Critical Graphs; 5.1 Critical Graphs With Many Edges; 5.2 Minimum Degree of 4- and 5-Critical Graphs; 5.3 Critical Graphs With Few Edges; 5.4 Four-Critical Amenable Graphs; 5.5 Four-Critical Degree 5 Problem 327 $a5.6 Large Critical Subgraphs of Critical Graphs5.7 Critical Subgraph Covering a 2-Path; 5.8 Noninduced Critical Subgraphs; 5.9 Number of Critical Subgraphs; 5.10 Subgraphs of Critical Graphs; 5.11 Minimal Circumference of Critical Graphs; 5.12 The Erdo?s-Lova?sz Tihany Problem; 5.13 Partial Joins of Critical Graphs; 5.14 Vertex-Critical Graphs Without Critical Edges; Bibliography; 6 The Conjectures of Hadwiger and Hajo?s; 6.1 Hadwiger's Conjecture; 6.2 Hajo?s' Conjecture; 6.3 The (m, n)- and [m, n]-Conjectures; 6.4 Hadwiger Degree of a Graph; 6.5 Graphs Without Odd-K5; 6.6 Scheme Conjecture 327 $a6.7 Chromatic 4-Schemes 330 $aContains a wealth of information previously scattered in research journals, conference proceedings and technical reports. Identifies more than 200 unsolved problems. Every problem is stated in a self-contained, extremely accessible format, followed by comments on its history, related results and literature. The book will stimulate research and help avoid efforts on solving already settled problems. Each chapter concludes with a comprehensive list of references which will lead readers to original sources, important contributions and other surveys. 410 0$aWiley-Interscience series in discrete mathematics and optimization. 606 $aGraph coloring 608 $aElectronic books. 615 0$aGraph coloring. 676 $a511.5 676 $a511/.5 700 $aJensen$b Tommy R.$0753649 702 $aToft$b Bjarne 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910141196003321 996 $aGraph coloring problems$91516178 997 $aUNINA