Colorings and orientations of graphs

DOI10.1007/BF01204715zbMath0756.05049WikidataQ56390729 ScholiaQ56390729MaRDI QIDQ1196681

Michael Tarsi, Noga Alon

Publication date: 16 January 1993

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

chromatic number; orientations; vertex-coloring

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C20: Directed graphs (digraphs), tournaments

Related Items

Coloring, sparseness and girth, Jacobsthal numbers in generalised Petersen graphs, Total weight choosability of Cartesian product of graphs, The Combinatorial Nullstellensätze revisited, Orientations of graphs with prescribed weighted out-degrees, On the choosability of claw-free perfect graphs, Period preserving properties of an invariant from the permanent of signed incidence matrices, Permanent index of matrices associated with graphs, List coloring of planar graphs with forbidden cycles, Total weight choosability of Mycielski graphs, Fundamental invariants of orbit closures, Every graph is \((2,3)\)-choosable, Dynamic list coloring of bipartite graphs, Distinguishing graphs by their left and right homomorphism profiles, On two generalizations of the Alon-Tarsi polynomial method, On 3-choosability of triangle-free plane graphs, On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs, List colourings of planar graphs, Nowhere-zero flow polynomials, On 3-colorings of plane graphs, Brooks' theorem via the Alon-Tarsi theorem, On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs, Delay colouring in quartic graphs, Circular list colorings of some graphs, Group coloring is \(\Pi_2^{\text{P}}\)-complete, Coloring problems on bipartite graphs of small diameter, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, Pfaffian labelings and signs of edge colorings, On 3-choosability of planar graphs without certain cycles, Lucky labelings of graphs, Ore-type versions of Brooks' theorem, The chromatic polynomial and list colorings, From a zoo to a zoology: Towards a general theory of graph polynomials, Restricted set addition: the exceptional case of the Erdős-Heilbronn conjecture, Some results on \((a:b)\)-choosability, On 3-choosable planar graphs of girth at least 4, Injective colorings of planar graphs with few colors, Planar graphs without 3-, 7-, and 8-cycles are 3-choosable, Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable, The complexity of planar graph choosability, List homomorphisms to reflexive graphs, A solution to a colouring problem of P. Erdős, Binary invariants and orientations of graphs, Sumsets in vector spaces over finite fields, The list chromatic numbers of some planar graphs, The graph polynomial and the number of proper vertex colorings, The 4-choosability of plane graphs without 4-cycles, Stable sets and polynomials, On the relations of various conjectures on Latin squares and straightening coefficients, Algorithmic complexity of list colorings, On even and odd latin squares, Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension, On the number of even and odd Latin squares of order \(p+1\), The Cayley determinant of the determinant tensor and the Alon-Tarsi conjecture, A note on graph colorings and graph polynomials, \(T\)-choosability in graphs, Chords of longest cycles in cubic graphs, On 3-choosability of plane graphs without 6-, 7- and 9-cycles, The oriented cycle game, Graphs are \((1, \varDelta + 1)\)-choosable, Planar graphs of girth at least five are square \((\delta + 2)\)-choosable, The Alon-Tarsi number of planar graphs, The List \(L(2, 1)\)-labeling of planar graphs, Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs, Efficient enumeration of graph orientations with sources, Choice numbers of multi-bridge graphs, Graphs with maximum average degree less than \(\frac{11}{4}\) are \((1, 3)\)-choosable, A step towards Yuzvinsky's conjecture, Integration formulas for Brownian motion on classical compact Lie groups, Square-root cancellation for the signs of Latin squares, Planar graphs without chordal 6-cycles are 4-choosable, Generalized list \(T\)-colorings of cycles, The 3-choosability of plane graphs of girth 4, A note on the DP-chromatic number of complete bipartite graphs, Choosability, edge choosability and total choosability of outerplane graphs, On structure of some plane graphs with application to choosability, Coloring face-hypergraphs of graphs on surfaces, Density via duality., On 2-coloring certain \(k\)-uniform hypergraphs, On the Dinitz conjecture and related conjectures, An exchange property of matroids, A not 3-choosable planar graph without 3-cycles, Choosability of planar graphs, Matrix choosability, Parity of transversals of Latin squares, Geometric conditions for \(\square\)-irreducibility of certain representations of the general linear group over a non-Archimedean local field, DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from \(\{6,7,8\}\), Combinatorial Nullstellensatz and DP-coloring of graphs, Injective choosability of subcubic planar graphs with girth 6, A condition for the existence of zero coefficients in the powers of the determinant polynomial, Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares, Answers to two questions on the DP color function, Differences between the list-coloring and DP-coloring for planar graphs, Isotopy graphs of Latin tableaux, A generalization of some results on list coloring and DP-coloring, The list edge coloring and list total coloring of planar graphs with maximum degree at least 7, The Alon-Tarsi number of a planar graph minus a matching, On the chromatic polynomial and counting DP-colorings of graphs, From the 1-2-3 conjecture to the Riemann hypothesis, 2-connected chordal graphs and line graphs are \((1,5)\)-choosable, The Dinitz problem solved for rectangles, Choice Numbers of Graphs: a Probabilistic Approach, Total choosability of multicircuits I, Total choosability of multicircuits II, 3-Paintability of planar graphs, Fair Representation by Independent Sets, Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count, On Zeros of a Polynomial in a Finite Grid, Coloration de graphes : fondements et applications, Unnamed Item, Short Proof of Galvin's Theorem on the List-chromatic Index of a Bipartite Multigraph, Discriminants, Symmetrized Graph Monomials, and Sums Of Squares, Total weight choosability for Halin graphs, No occurrence obstructions in geometric complexity theory, Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs, General Parity Result and Cycle‐Plus‐Triangles Graphs, A study of the representations supported by the orbit closure of the determinant, Mixing properties of colourings of the ℤ^d lattice, Total Weight Choosability of Trees, List-Coloring Claw-Free Graphs with $\Delta-1$ Colors, Two Chromatic Conjectures: One for Vertices and One for Edges, Total weight choosability of graphs, Amenable colorings, On the complexity of Hilbert refutations for partition, The minimum number of edges in a 4-critical graph that is bipartite plus 3 edges, Improved lower bounds on the number of edges in list critical and online list critical graphs, The Alon-Tarsi number of planar graphs without cycles of lengths 4 and \(l\), Chromatic number and orientations of graphs and signed graphs, 2-colorability of \(r\)-uniform hypergraphs, The Alon-Tarsi conjecture: a perspective on the main results, Note on 3-choosability of planar graphs with maximum degree 4, Computing the chromatic number using graph decompositions via matrix rank, Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs, Connections between conjectures of Alon-Tarsi, Hadamard-Howe, and integrals over the special unitary group, An algebraic criterion for the choosability of graphs, Geometric complexity theory: an introduction for geometers, Wreath determinants for group-subgroup pairs., Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry, An online version of Rota's basis conjecture, On DP-coloring of graphs and multigraphs, Recognizing \(d\)-interval graphs and \(d\)-track interval graphs, A sufficient condition for a planar graph to be 3-choosable, Planar graphs without intersecting 5-cycles are 4-choosable, Total weight choosability of graphs with bounded maximum average degree, DP-colorings of graphs with high chromatic number, Beyond degree choosability, \((4,2)\)-choosability of planar graphs with forbidden structures, A note on orientation and chromatic number of graphs, Perfect graphs, kernels, and cores of cooperative games, Extended skew partition problem, The game of arboricity, Algebraic characterization of uniquely vertex colorable graphs, Parity, Eulerian subgraphs and the Tutte polynomial, Bordeaux 3-color conjecture and 3-choosability, A relation between choosability and uniquely list colorability, List colourings of planar graphs. (Reprint), The odd case of Rota's bases conjecture, Completing partial proper colorings using Hall's condition, List edge colourings of some 1-factorable multigraphs, A note on 3-choosability of planar graphs without certain cycles, A compactness argument in the additive theory and the polynomial method., Painting squares in \(\Delta^2-1\) shades, Degeneracy and colorings of squares of planar graphs without 4-cycles, Semialgebraic graphs having countable list-chromatic numbers, Graph homomorphisms, the Tutte polynomial and “q-state Potts uniqueness”, Hownotto prove the Alon-Tarsi conjecture, Crypto Galore!, Permanent versus determinant: Not via saturations, Jacobsthal Numbers in Generalized Petersen Graphs, A note on 3-choosability of plane graphs under distance restrictions, THERE ARE ASYMPTOTICALLY THE SAME NUMBER OF LATIN SQUARES OF EACH PARITY, Some Combinatorial Applications of Gröbner Bases, Choosability of toroidal graphs without short cycles, Brooks' Theorem and Beyond, Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz, ADDITIVE BASES IN ABELIAN GROUPS, ON THE NUMBER OF LATIN RECTANGLES, Circular choosability via combinatorial Nullstellensatz, Weight choosability of graphs

Cites Work

• Unnamed Item
• Independence numbers of graphs and generators of ideals
• Regular subgraphs of almost regular graphs
• A nowhere-zero point in linear mappings
• On the decomposition of a graph into stars
• Acyclic orientations of graphs
• A note on list-colorings
• Tournaments and Vandermond's determinant
• On the Structure oft-Designs