General Parity Result and Cycle-plus-Triangles Graphs

2015/12/19 by Fedor V. Petrov, Petrov, Fedor V.
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1512.06205

arxiv created 2015/12/19 · arxiv updated 2015/12/22

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.

Related

• The Parity Hamiltonian Cycle Problem
• A reduction of the "cycles plus K₄'s" problem
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
• 3-Coloring on Regular, Planar, and Ordered Hamiltonian Graphs
• Almost Series-Parallel graphs: structure and colorability