Premium
General Parity Result and Cycle‐Plus‐Triangles Graphs
Author(s) -
Petrov Fedor
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22107
Subject(s) - combinatorics , mathematics , hamiltonian path , parity (physics) , disjoint sets , graph , discrete mathematics , physics , particle physics
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 show how a version of polynomial method gives slightly more combinatorial information about colorings than direct application of Alon's Combinatorial Nullstellensatz.