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 numberorientationsvertex-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items

Algorithmic complexity of list colorings, Graphs are \((1, \varDelta + 1)\)-choosable, Coloring problems on bipartite graphs of small diameter, Graph polynomials and paintability of plane graphs, Planar graphs of girth at least five are square \((\delta + 2)\)-choosable, The Alon-Tarsi number of planar graphs, On even and odd latin squares, Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension, The List \(L(2, 1)\)-labeling of planar graphs, Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs, Coloring, sparseness and girth, Jacobsthal numbers in generalised Petersen graphs, On the Dinitz conjecture and related conjectures, Efficient enumeration of graph orientations with sources, Choice numbers of multi-bridge graphs, An exchange property of matroids, A not 3-choosable planar graph without 3-cycles, 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, Graphs with maximum average degree less than \(\frac{11}{4}\) are \((1, 3)\)-choosable, A note on graph colorings and graph polynomials, Choosability of planar graphs, The complexity of planar graph choosability, \(T\)-choosability in graphs, A step towards Yuzvinsky's conjecture, List homomorphisms to reflexive graphs, Dynamic list coloring of bipartite graphs, Chords of longest cycles in cubic graphs, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, Integration formulas for Brownian motion on classical compact Lie groups, Square-root cancellation for the signs of Latin squares, Total weight choosability of Cartesian product of graphs, Distinguishing graphs by their left and right homomorphism profiles, On two generalizations of the Alon-Tarsi polynomial method, The Combinatorial Nullstellensätze revisited, On 3-choosability of plane graphs without 6-, 7- and 9-cycles, On 3-choosability of triangle-free plane graphs, Matrix choosability, Orientations of graphs with prescribed weighted out-degrees, On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs, On the choosability of claw-free perfect graphs, Parity of transversals of Latin squares, Pfaffian labelings and signs of edge colorings, 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, Geometric conditions for \(\square\)-irreducibility of certain representations of the general linear group over a non-Archimedean local field, Total weight choosability of Mycielski graphs, A solution to a colouring problem of P. Erdős, Binary invariants and orientations of graphs, Fundamental invariants of orbit closures, Every graph is \((2,3)\)-choosable, Planar graphs without chordal 6-cycles are 4-choosable, List colourings of planar graphs, DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from \(\{6,7,8\}\), On 3-choosability of planar graphs without certain cycles, Combinatorial Nullstellensatz and DP-coloring of graphs, Nowhere-zero flow polynomials, On 3-colorings of plane graphs, Injective choosability of subcubic planar graphs with girth 6, Generalized list \(T\)-colorings of cycles, Brooks' theorem via the Alon-Tarsi theorem, A condition for the existence of zero coefficients in the powers of the determinant polynomial, The 3-choosability of plane graphs of girth 4, Lucky labelings of graphs, A note on the DP-chromatic number of complete bipartite graphs, 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, On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs, Ore-type versions of Brooks' theorem, The chromatic polynomial and list colorings, Isotopy graphs of Latin tableaux, From a zoo to a zoology: Towards a general theory of graph polynomials, Sumsets in vector spaces over finite fields, 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, The Alon-Tarsi number of \(K_5\)-minor-free graphs, DP-\(4\)-colorability of planar graphs without intersecting \(5\)-cycles, The list chromatic numbers of some planar graphs, Alon-Tarsi numbers of direct products, 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, Choosability, edge choosability and total choosability of outerplane graphs, Delay colouring in quartic graphs, The graph polynomial and the number of proper vertex colorings, The complexity of finding fair independent sets in cycles, The oriented cycle game, Special case of Rota's basis conjecture on graphic matroids, On structure of some plane graphs with application to choosability, Coloring face-hypergraphs of graphs on surfaces, The 4-choosability of plane graphs without 4-cycles, Density via duality., Stable sets and polynomials, On 2-coloring certain \(k\)-uniform hypergraphs, On the relations of various conjectures on Latin squares and straightening coefficients, Circular list colorings of some graphs, Group coloring is \(\Pi_2^{\text{P}}\)-complete, Rota's basis conjecture for matroids with density close to one, A \((2, 1)\)-decomposition of planar graphs without intersecting 3-cycles and adjacent \(4^-\)-cycles, An algebraic formulation of hypergraph colorings, Decompositions of graphs of nonnegative characteristic with some forbidden subgraphs, On list \((p, 1)\)-total labellings of special planar graphs and 1-planar graphs, Stability of the Levi-Civita tensors and an Alon-Tarsi type theorem, 5-list coloring toroidal 6-regular triangulations in linear time, Orienting undirected phylogenetic networks, The Alon–Tarsi number of planar graphs revisited, The Alon-Tarsi number of two kinds of planar graphs, Sum-of-squares certificates for Vizing's conjecture via determining Gröbner bases, The Alon-Tarsi number of a toroidal grid, On the Alon-Tarsi number of semi-strong product of graphs, Schnyder woods and Alon-Tarsi number of planar graphs, A strengthening and an efficient implementation of Alon-Tarsi list coloring method, Unnamed Item, Hownotto prove the Alon-Tarsi conjecture, The choice number versus the chromatic number for graphs embeddable on orientable surfaces, On DP-coloring of graphs and multigraphs, Total choosability of multicircuits I, Total choosability of multicircuits II, Painting squares in \(\Delta^2-1\) shades, Recognizing \(d\)-interval graphs and \(d\)-track interval graphs, A sufficient condition for a planar graph to be 3-choosable, Crypto Galore!, The Dinitz problem solved for rectangles, Coloration de graphes : fondements et applications, 3-Paintability of planar graphs, Brooks' Theorem and Beyond, Choice Numbers of Graphs: a Probabilistic Approach, 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, Coloring linear hypergraphs: the Erdős-Faber-Lovász conjecture and the combinatorial nullstellensatz, Beyond degree choosability, Degeneracy and colorings of squares of planar graphs without 4-cycles, \((4,2)\)-choosability of planar graphs with forbidden structures, A note on orientation and chromatic number of graphs, Total Weight Choosability of Trees, List-Coloring Claw-Free Graphs with $\Delta-1$ Colors, Symmetric group characters of almost square shape, Covering almost all the layers of the hypercube with multiplicities, Permanent versus determinant: Not via saturations, Girth conditions and Rota's basis conjecture, Every planar graph with Δ ${\rm{\Delta }}$ ⩾ 8 is totally (Δ+2) $({\rm{\Delta }}+2)$‐choosable, Planar graphs without intersecting 5-cycles are signed-4-choosable, Single‐conflict colouring, A generalization of some results on list coloring and DP-coloring, Jacobsthal Numbers in Generalized Petersen Graphs, The list edge coloring and list total coloring of planar graphs with maximum degree at least 7, 4-choosability of planar graphs with 4-cycles far apart via the Combinatorial Nullstellensatz, The Alon-Tarsi number of a planar graph minus a matching, A note on 3-choosability of plane graphs under distance restrictions, Fair Representation by Independent Sets, Perfect graphs, kernels, and cores of cooperative games, Extended skew partition problem, Relation between the correspondence chromatic number and the Alon-Tarsi number, Short Proof of Galvin's Theorem on the List-chromatic Index of a Bipartite Multigraph, THERE ARE ASYMPTOTICALLY THE SAME NUMBER OF LATIN SQUARES OF EACH PARITY, Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count, On the chromatic polynomial and counting DP-colorings of graphs, Total weight choosability of graphs, From the 1-2-3 conjecture to the Riemann hypothesis, 2-connected chordal graphs and line graphs are \((1,5)\)-choosable, On Zeros of a Polynomial in a Finite Grid, Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz, Computing the Chromatic Number Using Graph Decompositions via Matrix Rank, Discriminants, Symmetrized Graph Monomials, and Sums Of Squares, Some Combinatorial Applications of Gröbner Bases, The game of arboricity, Algebraic characterization of uniquely vertex colorable graphs, On the complexity of Hilbert refutations for partition, The minimum number of edges in a 4-critical graph that is bipartite plus 3 edges, ADDITIVE BASES IN ABELIAN GROUPS, Parity, Eulerian subgraphs and the Tutte polynomial, ON THE NUMBER OF LATIN RECTANGLES, Bordeaux 3-color conjecture and 3-choosability, Amenable colorings, A relation between choosability and uniquely list colorability, List colourings of planar graphs. (Reprint), Choosability of toroidal graphs without short cycles, Semialgebraic graphs having countable list-chromatic numbers, Circular choosability via combinatorial Nullstellensatz, Weight choosability of graphs, Improved lower bounds on the number of edges in list critical and online list critical graphs, Total weight choosability for Halin graphs, The odd case of Rota's bases conjecture, Completing partial proper colorings using Hall's condition, No occurrence obstructions in geometric complexity theory, Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs, The Alon-Tarsi number of planar graphs without cycles of lengths 4 and \(l\), General Parity Result and Cycle‐Plus‐Triangles Graphs, A study of the representations supported by the orbit closure of the determinant, 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, Mixing properties of colourings of the ℤ^d lattice, Note on 3-choosability of planar graphs with maximum degree 4, List edge colourings of some 1-factorable multigraphs, A note on 3-choosability of planar graphs without certain cycles, Computing the chromatic number using graph decompositions via matrix rank, Graph homomorphisms, the Tutte polynomial and “q-state Potts uniqueness”, Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs, Two Chromatic Conjectures: One for Vertices and One for Edges, Tensor slice rank and Cayley's first hyperdeterminant, A compactness argument in the additive theory and the polynomial method., 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., The polynomial method for list-colouring extendability of outerplanar graphs, Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry, An inequality in mixed multiplicities, An online version of Rota's basis conjecture, On \((3, r)\)-choosability of some planar 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