A remark on a result on odd colorings of planar graphs

Pradhan, Dinabandhu (author), Sharma, Vaishali (author), Škrekovski, Riste (author)

A proper $k$-coloring of a graph is said to be odd if every non-isolated vertex has a color that appears an odd number of times on its neighborhood. Miao et al. (2024) [2] claimed that every planar graph without adjacent $3$-cycles is odd $7$-colorable and every triangle-free planar graph without intersecting $4$-cycles is odd $5$-colorable. Here, we point out that their published proof contains a fundamental flaw which affects the validity of the main results.

• Language: English
• Keywords: coloring, odd coloring, planar graphs
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.06.2026
• Year: 2026
• Number of pages: 5 str.
• Numbering: Vol. 349, iss. 6, art. no. 115014
• PID: 20.500.12556/RUL-179007
• UDC: 519.17
• ISSN on article: 0012-365X
• DOI: 10.1016/j.disc.2026.115014
• COBISS.SI-ID: 266953475
• Publication date in RUL: 03.02.2026

Record is a part of a journal

• Title: Discrete mathematics
• Shortened title: Discrete math.
• Publisher: Elsevier
• ISSN: 0012-365X
• COBISS.SI-ID: 1118479

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Projects

• Funder: ARIS - Slovenian Research and Innovation Agency
• Project number: P1-0383
• Name: Kompleksna omrežja