General parity result and cycle-plus-triangles graphs

DOI10.1002/JGT.22107MaRDI QIDQ4978447zbMATH OpenOpenAlexFDO

Authors F. V. Petrov

Publication date 10 August 2017

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

paritypolynomial methodgraph choosability

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: We generalize a parity result of Fleishner and Stiebitz that being combined with Alon--Tarsi polynomial method allowed them to prove that a 4-regular graph formed by a Hamiltonian cycle and several disjoint triangles is always 3-choosable. Also we present a modification of polynomial method and show how it gives slightly more combinatorial information about colourings than direct application of Alon's Combinatorial Nullstellensatz.

Recommendations

• scientific article; zbMATH DE number 524136
• On two generalizations of the Alon-Tarsi polynomial method
• On 3-choosability of triangle-free plane graphs
• scientific article; zbMATH DE number 970801
• Planar graphs without triangular 4-cycles are 3-choosable

Cites work

• A generalization of combinatorial Nullstellensatz
• A solution to a colouring problem of P. Erdős
• Colorings and orientations of graphs
• Combinatorial Nullstellensatz
• Partitions of nonzero elements of a finite field into pairs

Cited in

(2)

• An algorithm for identifying cycle-plus-triangles graphs
• Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs

This page was built for publication: General parity result and cycle-plus-triangles graphs

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