Gröbner bases techniques for an S-packing k-coloring of a graph

MaRDI QIDQ2401415zbMATH OpenFDO

Authors Hamid Maârouf

Publication date 8 September 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p33

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(S\)-packing coloringsGröbner basisShape's lemmazero dimensional ideal

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Solving polynomial systems; resultants (13P15)

Review text

In this interesting paper, the author uses combinatorial commutative algebra theory to study the problem of the \(S\)-packing coloring of a finite undirected and unweighted graph by introducing a family of polynomials encoding the problem. A method to find the \(S\)-packing colorings of the graph is presented and illustrated by examples.

Recommendations

• Gröbner bases and graph colorings
• On the packing coloring of base-3 Sierpiński graphs and \(H\)-graphs
• A note on Gröbner bases and graph colorings
• Packing coloring of generalized Sierpinski graphs
• On packing \(S\)-colorings of subcubic graphs
• \(S\)-packing colorings of cubic graphs
• Packing coloring of Sierpiński-type graphs
• scientific article; zbMATH DE number 6500342
• \(S\)-packing colorings of distance graphs \(G ( \mathbb{Z} , \{ 2 , t \} )\)
• Packing chromatic number of base-3 Sierpiński graphs

Cites work

• A graph coloring algorithm for large scheduling problems
• A new efficient algorithm for computing Gröbner bases (F₄)
• A new incremental algorithm for computing Groebner bases
• Algebraic characterization of uniquely vertex colorable graphs
• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems
• Gröbner bases and graph colorings
• Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
• scientific article; zbMATH DE number 4132308 (Why is no real title available?)
• scientific article; zbMATH DE number 6118222 (Why is no real title available?)
• scientific article; zbMATH DE number 3941661 (Why is no real title available?)
• scientific article; zbMATH DE number 1515218 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• scientific article; zbMATH DE number 217454 (Why is no real title available?)
• Recognizing graph theoretic properties with polynomial ideals
• The $L(2,1)$-Labeling Problem on Graphs
• The S-packing chromatic number of a graph

Cited in

(8)

• A general approach to deriving the \(g\)-good-neighbor conditional diagnosability of interconnection networks
• Gröbner bases and graph colorings
• \(S\)-packing chromatic vertex-critical graphs
• On the packing coloring of base-3 Sierpiński graphs and \(H\)-graphs
• On \(S\)-packing colourings of distance graphs \(D (1, t)\) and \(D (1, 2, t)\)
• scientific article; zbMATH DE number 6500342 (Why is no real title available?)
• A note on Gröbner bases and graph colorings
• Algebraic and combinatorial algorithms for S-packing coloring

This page was built for publication: Gröbner bases techniques for an \(S\)-packing \(k\)-coloring of a graph

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