On two generalizations of the Alon-Tarsi polynomial method

DOI10.1016/J.JCTB.2010.12.007zbMATH Open1234.05086arXiv0911.2099OpenAlexW2041832100MaRDI QIDQ651032FDOQ651032

Authors: Dan Hefetz Edit this on Wikidata

Publication date: 8 December 2011

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: In a seminal paper, Alon and Tarsi have introduced an algebraic technique for proving upper bounds on the choice number of graphs (and thus, in particular, upper bounds on their chromatic number). The upper bound on the choice number of $G$ obtained via their method, was later coined the emph{Alon-Tarsi number of $G$} and was denoted by $AT(G)$. They have provided a combinatorial interpretation of this parameter in terms of the eulerian subdigraphs of an appropriate orientation of $G$. Their characterization can be restated as follows. Let $D$ be an orientation of $G$. Assign a weight $omeg{a}_D(H)$ to every subdigraph $H$ of $D$: if $HsubseteqD$ is eulerian, then $omeg{a}_D(H)=(-1{)}^{e(H)}$, otherwise $omeg{a}_D(H)=0$. Alon and Tarsi proved that $AT(G)leqk$ if and only if there exists an orientation $D$ of $G$ in which the out-degree of every vertex is strictly less than $k$, and moreover $su{m}_{HsubseteqD}omeg{a}_D(H)eq0$. Shortly afterwards, for the special case of line graphs of $d$-regular $d$-edge-colorable graphs, Alon gave another interpretation of $AT(G)$, this time in terms of the signed $d$-colorings of the line graph. In this paper we generalize both results. The first characterization is generalized by showing that there is an infinite family of weight functions (which includes the one considered by Alon and Tarsi), each of which can be used to characterize $AT(G)$. The second characterization is generalized to all graphs (in fact the result is even more general -- in particular it applies to hypergraphs). We then use the second generalization to prove that $chi(G)=ch(G)=AT(G)$ holds for certain families of graphs $G$. Some of these results generalize certain known choosability results.

Full work available at URL: https://arxiv.org/abs/0911.2099

Recommendations

• scientific article; zbMATH DE number 3872575
• On the generalization of the Alefeld-Herzberger's method
• On generalization of tchebycheff polynomials
• Generalized Alternating Polynomials, some Properties and Numerical Applications
• scientific article; zbMATH DE number 3910975
• An Algebraic-Geometric Method for Computing Zolotarev Polynomials
• scientific article; zbMATH DE number 1175366
• scientific article; zbMATH DE number 3931642
• scientific article; zbMATH DE number 1121099
• Algebraic Methods for Modified Orthogonal Polynomials

zbMATH Keywords

list coloringpolynomial methodcombinatorial Nullstellensatzuniquely colorable graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Cites Work

• Mr. Paint and Mrs. Correct
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial Nullstellensatz
• The list chromatic index of a bipartite multigraph
• List edge colourings of some 1-factorable multigraphs
• Multicriterial graph problems with MAXMIN criterion
• Title not available (Why is that?)
• A nowhere-zero point in linear mappings
• Colorings and orientations of graphs
• The number of edge 3-colorings of a planar cubic graph as a permanent
• On-line list colouring of graphs
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
• Uniquely Colourable Graphs with Large Girth
• Anti‐magic graphs via the Combinatorial NullStellenSatz
• A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs
• Brooks' theorem via the Alon-Tarsi theorem
• Uniquely colorable graphs
• The size of uniquely colorable graphs
• On uniquely colorable planar graphs
• Asymptotically good list-colorings
• Independence numbers of graphs and generators of ideals
• A solution to a colouring problem of P. Erdős
• List \(T\)-colorings of graphs
• Choosability of powers of circuits
• On the Penrose number of cubic diagrams
• The graph polynomial and the number of proper vertex colorings
• A note on graph colorings and graph polynomials
• \(T\)-choosability in graphs
• \(K_r\)-free uniquely vertex colorable graphs with minimum possible edges
• Hypergraph extension of the Alon-Tarsi list coloring theorem
• A relation between choosability and uniquely list colorability
• Bounding the Independence Number of a Graph
• Construction of uniquely vertex k-colorable graphs with minimum possible size

Cited In (22)

• The Alon-Tarsi number of a toroidal grid
• List-coloring claw-free graphs with \(\Delta-1\) colors
• The Alon–Tarsi number of planar graphs revisited
• The Alon-Tarsi number of planar graphs
• Combinatorial Nullstellensatz and DP-coloring of graphs
• The Alon-Tarsi number of two kinds of planar graphs
• Hypergraph extension of the Alon-Tarsi list coloring theorem
• An algebraic criterion for the choosability of graphs
• Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs
• An alternative approach in generating a 2-variable very strictly Hurwitz polynomial (VSHP) and its application
• The Alon-Tarsi number of a planar graph minus a matching
• A note on Alon-Tarsi number of Halin graphs
• 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
• General parity result and cycle-plus-triangles graphs
• Alon-Tarsi numbers of direct products
• On list \((p, 1)\)-total labellings of special planar graphs and 1-planar graphs
• On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs
• On the generalization of the Alefeld-Herzberger's method
• An Alon-Tarsi style theorem for additive colorings
• Colorings and orientations of matrices and graphs

This page was built for publication: On two generalizations of the Alon-Tarsi polynomial method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q651032)