The Polynomial Method for Three-Path Extendability of List Colourings of Planar Graphs

被引：0

作者：

Gordinowicz, Przemyslaw ^{[1
]}

Twardowski, Pawel ^{[1
]}

机构：

[1] Lodz Univ Technol, Inst Math, Lodz, Poland

来源：

JOURNAL OF GRAPH THEORY | 2025年

关键词：

Alon-Tarsi number; graph polynomial; list colouring; planar graph; ALON-TARSI NUMBER; 5-LIST-COLORING GRAPHS;

D O I：

10.1002/jgt.23214

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We restate Thomassen's theorem of 3-extendability (Thomassen, Journal of Combinatorial Theory Series B, 97, 571-583), an extension of the famous planar 5-choosability theorem, in terms of graph polynomials. This yields an Alon-Tarsi equivalent of 3-extendability.

引用

页数：18

共 4 条

[1] The polynomial method for list-colouring extendability of outerplanar graphs
Gordinowicz, Przemyslaw
Twardowski, Pawel
ARS MATHEMATICA CONTEMPORANEA, 2021, 21 (02)
[2] List-edge-coloring of planar graphs without 6-cycles with three chords
Wang, Haiying
Wu, Jianliang
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 35 (02) : 555 - 562
[3] List-edge-coloring of planar graphs without 6-cycles with three chords
Haiying Wang
Jianliang Wu
Journal of Combinatorial Optimization, 2018, 35 : 555 - 562
[4] Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs
Abrishami, G.
Rahbarnia, E.
INFORMATION PROCESSING LETTERS, 2018, 140 : 25 - 29

← 1 →