General parity result and cycle-plus-triangles graphs

DOI10.1002/JGT.22107zbMATH Open1368.05054arXiv1512.06205OpenAlexW2962702708MaRDI QIDQ4978447FDOQ4978447

Authors: F. V. Petrov 

Publication date: 10 August 2017

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

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.

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

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

zbMATH Keywords

paritypolynomial methodgraph choosability

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs
• An algorithm for identifying cycle-plus-triangles 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)