scientific article; zbMATH DE number 821271
From MaRDI portal
Publication:4857375
zbMath0855.05054MaRDI QIDQ4857375
Publication date: 28 November 1995
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
graph coloringplanar graphshypergraphsflowsperfect graphscritical graphsharmonious chromatic numberorientationsgame chromatic numberdegreeschromatic polynomialssparse graphsedge coloringslist-coloringcombinatorial graphschromatic graphsconjectures of Hadwiger
Related Items
The incidentor coloring of multigraphs and its applications, A note on the minimum number of choosability of planar graphs, Total coloring of planar graphs without chordal 7-cycles, List-edge-colouring planar graphs with precoloured edges, Thinness of product graphs, A note on total and list edge-colouring of graphs of tree-width 3, The Alon-Tarsi number of planar graphs, Dynamic \(F\)-free coloring of graphs, Three-coloring planar graphs without short cycles, The tournament scheduling problem with absences, On the \(d\)-distance face chromatic number of plane graphs, List edge and list total coloring of planar graphs with maximum degree 8, The number of \(k\)-colorings of a graph on a fixed surface, Solving graph coloring problems with the Douglas-Rachford algorithm, Hamiltonicity and colorings of arrangement graphs, Hamiltonian cycles in critical graphs with large maximum degree, Steinberg's conjecture is false, The number of colorings of planar graphs with no separating triangles, Total colorings of embedded graphs with no 3-cycles adjacent to 4-cycles, The equivalence number of a line graph, Modularity-based decompositions for valued CSP, Color-critical graphs on a fixed surface, A note on graph colorings and graph polynomials, Group connectivity of bridged graphs, Graph factors and factorization: 1985--2003: a survey, Online multi-coloring on the path revisited, Partitions of graphs into cographs, \(L(2,1)\)-labelings on the modular product of two graphs, NP-completeness of local colorings of graphs, Total coloring of embedded graphs with maximum degree at least seven, The square of a planar cubic graph is 7-colorable, (\(1,1,0\))-coloring of planar graphs without cycles of length 4 and 6, Cellular adaptive Petri net based on learning automata and its application to the vertex coloring problem, Spanning quadrangulations of triangulated surfaces, Packing six \(T\)-joins in plane graphs, On the edge-density of 4-critical graphs, On indicated coloring of graphs, Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs, Parity vertex colouring of plane graphs, The chromatic number of a graph of girth 5 on a fixed surface, A new lower bound on the number of edges in colour-critical graphs and hypergraphs, Tension continuous maps -- their structure and applications, The list-chromatic number of infinite graphs defined on Euclidean spaces, Online variable-sized bin packing with conflicts, Goodness of fit tests for a class of Markov random field models, On two generalizations of the Alon-Tarsi polynomial method, Nowhere-zero 3-flows and modulo \(k\)-orientations, Ore's conjecture on color-critical graphs is almost true, A note on vertex colorings of plane graphs, Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker, On the induced matching problem, List 2-facial 5-colorability of plane graphs with girth at least 12, On the construction of non-2-colorable uniform hypergraphs, On-line choice number of complete multipartite graphs: an algorithmic approach, Clique colourings of geometric graphs, On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs, Distance constraints on short cycles for 3-colorability of planar graphs, Coloring clique-hypergraphs of graphs with no subdivision of \(K_5\), Hedetniemi's conjecture for uncountable graphs, Maximum cardinality neighbourly sets in quadrilateral free graphs, More bounds for the Grundy number of graphs, Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree, Interval edge-colorings of composition of graphs, The behavior of clique-width under graph operations and graph transformations, The edge density of critical digraphs, List edge and list total coloring of 1-planar graphs, On the page number of RNA secondary structures with pseudoknots, On minimal triangle-free graphs with prescribed \(k\)-defective chromatic number, Solving a multicoloring problem with overlaps using integer programming, Interval edge-colorings of complete graphs and \(n\)-dimensional cubes, Color-critical graphs have logarithmic circumference, List edge and list total colorings of planar graphs without short cycles, Some remarks on Hajós' conjecture, On 3-colorability of planar graphs without adjacent short cycles, What is on his mind?, The thickness and chromatic number of \(r\)-inflated graphs, On topological relaxations of chromatic conjectures, Minimum choosability of planar graphs, \(K_3\)-WORM colorings of graphs: lower chromatic number and gaps in the chromatic spectrum, Edge-choosability of planar graphs without adjacent triangles or without 7-cycles, A note on list improper coloring of plane graphs, Randić index and coloring number of a graph, A larger family of planar graphs that satisfy the total coloring conjecture, Proof of the list edge coloring conjecture for complete graphs of prime degree, Minimum entropy coloring, 4-chromatic edge critical Grötzsch-Sachs graphs, Decomposing a planar graph of girth 5 into an independent set and a forest, Note on coloring graphs without odd-\(K_k\)-minors, On the hardness of allocating frequencies for hybrid networks, Coloring graphs with sparse neighborhoods, On the deficiency of bipartite graphs, Total colorings and list total colorings of planar graphs without intersecting 4-cycles, 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six and \(\varDelta \geq 18\), Chromatic numbers of simplicial manifolds, Edge-disjoint odd cycles in graphs with small chromatic numbers, On cyclic colorings and their generalizations, The harmonious chromatic number of complete \(r\)-ary trees, The game coloring number of planar graphs, A strengthening of Brooks' theorem, Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees, The number of disjoint perfect matchings in semi-regular graphs, Lexbfs-orderings and powers of hhd-free graphs∗, Powers of hhd-free graphs∗, AmgX: A Library for GPU Accelerated Algebraic Multigrid and Preconditioned Iterative Methods, One-sided interval edge-colorings of bipartite graphs, Clique-coloring claw-free graphs, Unnamed Item, Hierarchical and modularly-minimal vertex colorings, Unnamed Item, Primal-dual approximation algorithms for feedback problems in planar graphs, On δ(k)-coloring of generalized Petersen graphs, On δ(k)-coloring of powers of helm and closed helm graphs, On certain coloring parameters of Mycielski graphs of some graphs, Equitable coloring parameters of certain graph classes, Hyperbolic families and coloring graphs on surfaces, The $\chi$-Ramsey Problem for Triangle-Free Graphs, Questions on color-critical subgraphs, Edge DP-coloring in planar graphs, The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices, A note on one-sided interval edge colorings of bipartite graphs, Colouring square-free graphs without long induced paths., Planar graphs with $\Delta\geq 8$ are ($\Delta+1$)-edge-choosable, Hadwiger's Conjecture for Graphs with Forbidden Holes, Very Large-Scale Neighborhood Search: Overview and Case Studies on Coloring Problems, On some properties of 4‐regular plane graphs, Graph coloring with no large monochromatic components, New bounds for the chromatic number of graphs, A conjecture of Borodin and a coloring of Grünbaum, An improved bound for the strong chromatic number, On b-acyclic chromatic number of a graph, Forbidden lifts (NP and CSP for combinatorialists), Local 7-coloring for planar subgraphs of unit disk graphs, On chromatic Zagreb indices of certain graphs, Using Brouwer’s Fixed Point Theorem, On the minimum size of 4-uniform hypergraphs without property \(B\), The list-chromatic index of \(K_6\), On certain parameters of equitable coloring of graphs, On the sum of a Sobolev space and a weighted \(L_p\)-space, Relation between the correspondence chromatic number and the Alon-Tarsi number, Graph coloring approach with new upper bounds for the chromatic number: team building application, A unified approach to distance-two colouring of graphs on surfaces, Towards an on-line version of Ohba's conjecture, Short proofs of coloring theorems on planar graphs, Clique-transversal sets and clique-coloring in planar graphs, Distance-two coloring of sparse graphs, A survey of graph coloring - its types, methods and applications, Maximum cuts of graphs with forbidden cycles, Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs, Linear colorings of subcubic graphs, New results on two hypercube coloring problems, A note on graphs contraction-critical with respect to independence number, Fulkerson's conjecture and Loupekine snarks, Rainbow neighbourhood number of graphs, Discrete Mesh Optimization on GPU, An immune algorithm with stochastic aging and Kullback entropy for the chromatic number problem, Computing the Chromatic Number Using Graph Decompositions via Matrix Rank, The chromatic number of the square of the $8$-cube, Further results on Erdős–Faber–Lovász conjecture, List Coloring of Two Matroids through Reduction to Partition Matroids, Distance graphs on \(\mathbb R^n\) with 1-norm, Planar graphs without 4, 6, 8-cycles are 3-colorable, Acyclic 4‐Choosability of Planar Graphs with No 4‐ and 5‐Cycles, Local edge coloring of graphs, Counterexamples to Grötzsch-Sachs-Koester's conjecture, A branch-and-cut algorithm for graph coloring, Finite subgraphs of uncountably chromatic graphs, The acyclic edge chromatic number of a random d‐regular graph is d + 1, On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs, Unnamed Item, On the Max Coloring Problem, Semialgebraic graphs having countable list-chromatic numbers, A local Lagrange interpolation method based on $C^{1}$ cubic splines on Freudenthal partitions, Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable, Edge coloring multigraphs without small dense subsets, On Injective Colourings of Chordal Graphs, MAXIMUM CUTS IN GRAPHS WITHOUT WHEELS, The Second-Moment Phenomenon for Monochromatic Subgraphs, Improper colouring of graphs with no odd clique minor, A study on the injective coloring parameters of certain graphs, BIPARTITE SUBGRAPHS OF -FREE GRAPHS, Hypergraph list coloring and Euclidean Ramsey theory, Colouring (P_r+P_s)-Free Graphs, Hadwiger’s Conjecture, Colouring H-free graphs of bounded diameter., Fractional Coloring Methods with Applications to Degenerate Graphs and Graphs on Surfaces, Shearer's point process, the hard-sphere model, and a continuum Lovász local lemma, From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces, Vehicle Sequencing at Transshipment Terminals with Handover Relations, On the Anderson-Lipman conjecture and some related problems, A new upper bound on the cyclic chromatic number, Total chromatic number of planar graphs with maximum degree ten, Acyclic choosability of planar graphs: a Steinberg like approach, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, On the complexity of unfrozen problems, Locally restricted colorings, Subdivision of the hierarchy of H-colorable graph classes by circulant graphs, A Conjecture of Borodin and a Coloring of Grünbaum, Distance Labelling Problems for Hypercubes and Hamming Graphs – A Survey, An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem, The Empire Problem in Even Embeddings on Closed Surfaces, On indicated chromatic number of graphs, Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant, The complexity of signed graph and edge-coloured graph homomorphisms, A new upper bound on the chromatic number of graphs with no odd \(K_t\) minor, On the chromatic number of some geometric type Kneser graphs, Zero-divisor graphs and total coloring conjecture, On indicated coloring of lexicographic product of graphs, Graph coloring and semidefinite rank, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, On interval and cyclic interval edge colorings of \((3, 5)\)-biregular graphs, Facially-constrained colorings of plane graphs: a survey, On acyclic colorings of graphs on surfaces, Graph \(r\)-hued colorings -- a survey, Critical graphs for the chromatic edge-stability number, Every planar graph without triangles adjacent to cycles of length 3 or 6 is \(( 1 , 1 , 1 )\)-colorable, An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm, An exact algorithm for the edge coloring by total labeling problem, Construction of Barnette graphs whose large subgraphs are non-Hamiltonian, A note on orientation and chromatic number of graphs, On \(J\)-colorability of certain derived graph classes, On some \(L(2, 1)\)-coloring parameters of certain graph classes, A new approach to the chromatic number of the square of Kneser graph \(K(2k+1,k)\), Colouring \((P_r + P_s)\)-free graphs, Bipartite induced density in triangle-free graphs, New restrictions on defective coloring with applications to Steinberg-type graphs, The structure of plane graphs with independent crossings and its applications to coloring problems, Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable, The list chromatic index of simple graphs whose odd cycles intersect in at most one edge, On the complexity of restoring corrupted colorings, Optimal channel assignment with list-edge coloring, The list edge coloring and list total coloring of planar graphs with maximum degree at least 7, \(S\)-packing chromatic vertex-critical graphs, The Alon-Tarsi number of a planar graph minus a matching, List-edge-coloring of planar graphs without 6-cycles with three chords, Computational aspects of greedy partitioning of graphs, Planar graphs without 4- and 5-cycles are acyclically 4-choosable, Colouring of \((P_3 \cup P_2)\)-free graphs, Star coloring of certain graph classes, Computing the list chromatic index of graphs, Characterization of forbidden subgraphs for bounded star chromatic number, On the cyclic coloring conjecture, List edge coloring of planar graphs without 6-cycles with two chords, Uncolorable mixed hypergraphs, On the number of edges in hypergraphs critical with respect to strong colourings, Maximum cuts in \(\mathscr{H} \)-free graphs, Decomposition of cubic graphs related to Wegner's conjecture, Improper interval edge colorings of graphs, Coloring temporal graphs, Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem, Total-coloring of sparse graphs with maximum degree 6, Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs, A structure of 1-planar graph and its applications to coloring problems, New potential functions for greedy independence and coloring, Combinatorial Nullstellensatz and DP-coloring of graphs, Bipartite graphs whose squares are not chromatic-choosable, Acyclic colorings of locally planar graphs, List total colorings of series-parallel graphs, Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph, List edge coloring of outer-1-planar graphs, Cyclic deficiency of graphs, A note on the chromatic number of the square of Kneser graph \(K(2 k + 1, k)\), A sufficient condition for planar graphs with maximum degree 6 to be totally 8-colorable, \(J\)-coloring of graph operations, Factorizing regular graphs, Structure and colour in triangle-free graphs, Sobolev functions on closed subsets of the real line, Equitable coloring of some convex polytope graphs, Exact distance graphs of product graphs, Injective coloring of Halin graphs, A linear-time algorithm for clique-coloring planar graphs, On \(t\)-relaxed 2-distant circular coloring of graphs, Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs, About graph mappings, The Alon-Tarsi number of planar graphs without cycles of lengths 4 and \(l\), A game theoretic framework for software diversity for network security, Some remarks on interval colorings of complete tripartite and biregular graphs, Group connectivity and group coloring: small groups versus large groups, Hajós and Ore constructions for digraphs, Facial rainbow coloring of plane graphs, Counting critical subgraphs in \(k\)-critical graphs, Nowhere-zero 3-flows in toroidal graphs, Measurable versions of the Lovász local lemma and measurable graph colorings, The Alon-Tarsi number of \(K_5\)-minor-free graphs, Monochromatic subgraphs in randomly colored graphons, Colouring square-free graphs without long induced paths, Total coloring of recursive maximal planar graphs, Computing the chromatic number using graph decompositions via matrix rank, The clique-perfectness and clique-coloring of outer-planar graphs, Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs, Deciding \(k\)-colorability in expected polynomial time, Odd Hadwiger for line-graphs, Tools for counting odd cycles in graphs, Surfaces, tree-width, clique-minors, and partitions, A new bound on the cyclic chromatic number, Decomposing a planar graph into an independent set and a 3-degenerate graph, Patch colorings and rigid colorings of the rational \(n\)-space, 2-distance colorings of some direct products of paths and cycles, Distributed coloring algorithms for triangle-free graphs, Partitioning planar graphs without 4-cycles and 6-cycles into a linear forest and a forest, List edge coloring of planar graphs without non-induced 6-cycles, Improved bound for improper colourings of graphs with no odd clique minor, A new 4-chromatic edge critical Koester graph, Decomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules, Every planar graph with Δ ${\rm{\Delta }}$ ⩾ 8 is totally (Δ+2) $({\rm{\Delta }}+2)$‐choosable, A note on \(\Delta\)-critical graphs, A note on Reed's conjecture for triangle-free graphs, A \((2, 1)\)-decomposition of planar graphs without intersecting 3-cycles and adjacent \(4^-\)-cycles, Graph and hypergraph colouring via nibble methods: a survey, Solving combinatorial optimisation problems using oscillator based Ising machines, Decompositions of graphs of nonnegative characteristic with some forbidden subgraphs, Minimum gradation in greyscales of graphs, Hardness transitions and uniqueness of acyclic colouring, The Alon-Tarsi number of two kinds of planar graphs, Unnamed Item, Extensions and reductions of squarefree words, Chromatic numbers of Cayley graphs of abelian groups: a matrix method, On the Alon-Tarsi number of semi-strong product of graphs, On triangle-free list assignments, Edge-colouring graphs with local list sizes, Schnyder woods and Alon-Tarsi number of planar graphs, Unnamed Item, Unnamed Item, Strong Turán stability, A note on δ^(k)-colouring of the Cartesian product of some graphs, Frozen development in graph coloring, Labeling trees with a condition at distance two, Colouring graphs of bounded diameter in the absence of small cycles, Relaxing the irrevocability requirement for online graph algorithms, Colouring graphs of bounded diameter in the absence of small cycles, Claw‐decompositions and tutte‐orientations, Unnamed Item, Unnamed Item, Unnamed Item, Interval Non‐edge‐Colorable Bipartite Graphs and Multigraphs, Parameterized Pre-Coloring Extension and List Coloring Problems, Unnamed Item, A brief history of edge-colorings – with personal reminiscences, On b-coloring of central graph of some graphs, Maximum bipartite subgraphs in $H$-free graphs
