---
OA_place: publisher
OA_type: hybrid
_id: '19879'
abstract:
- lang: eng
  text: We consider the 4-precoloring extension problem in planar near-Eulerian- triangulations,
    i.e., plane graphs where all faces except possibly for the outer one have length
    three, all vertices not incident with the outer face have even degree, and exactly
    the vertices incident with the outer face are precolored. We give a necessary
    topological condition for the precoloring to extend, and give a complete characterization
    when the outer face has length at most five and when all vertices of the outer
    face have odd degree and are colored using only three colors.
acknowledgement: Supported by project 22-17398S (Flows and cycles in graphs on surfaces)
  of Czech Science Foundation. An extended abstract appeared in Proceedings of the
  12th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’23)
article_number: '104138'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Zdeněk
  full_name: Dvořák, Zdeněk
  last_name: Dvořák
- first_name: Benjamin
  full_name: Moore, Benjamin
  id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
  last_name: Moore
- first_name: Michaela
  full_name: Seifrtová, Michaela
  last_name: Seifrtová
- first_name: Robert
  full_name: Šámal, Robert
  last_name: Šámal
citation:
  ama: Dvořák Z, Moore B, Seifrtová M, Šámal R. Precoloring extension in planar near-Eulerian-triangulations.
    <i>European Journal of Combinatorics</i>. 2025;127. doi:<a href="https://doi.org/10.1016/j.ejc.2025.104138">10.1016/j.ejc.2025.104138</a>
  apa: Dvořák, Z., Moore, B., Seifrtová, M., &#38; Šámal, R. (2025). Precoloring extension
    in planar near-Eulerian-triangulations. <i>European Journal of Combinatorics</i>.
    Elsevier. <a href="https://doi.org/10.1016/j.ejc.2025.104138">https://doi.org/10.1016/j.ejc.2025.104138</a>
  chicago: Dvořák, Zdeněk, Benjamin Moore, Michaela Seifrtová, and Robert Šámal. “Precoloring
    Extension in Planar Near-Eulerian-Triangulations.” <i>European Journal of Combinatorics</i>.
    Elsevier, 2025. <a href="https://doi.org/10.1016/j.ejc.2025.104138">https://doi.org/10.1016/j.ejc.2025.104138</a>.
  ieee: Z. Dvořák, B. Moore, M. Seifrtová, and R. Šámal, “Precoloring extension in
    planar near-Eulerian-triangulations,” <i>European Journal of Combinatorics</i>,
    vol. 127. Elsevier, 2025.
  ista: Dvořák Z, Moore B, Seifrtová M, Šámal R. 2025. Precoloring extension in planar
    near-Eulerian-triangulations. European Journal of Combinatorics. 127, 104138.
  mla: Dvořák, Zdeněk, et al. “Precoloring Extension in Planar Near-Eulerian-Triangulations.”
    <i>European Journal of Combinatorics</i>, vol. 127, 104138, Elsevier, 2025, doi:<a
    href="https://doi.org/10.1016/j.ejc.2025.104138">10.1016/j.ejc.2025.104138</a>.
  short: Z. Dvořák, B. Moore, M. Seifrtová, R. Šámal, European Journal of Combinatorics
    127 (2025).
corr_author: '1'
date_created: 2025-06-23T13:54:46Z
date_published: 2025-06-01T00:00:00Z
date_updated: 2025-09-30T13:42:59Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2025.104138
external_id:
  arxiv:
  - '2312.13061'
  isi:
  - '001443061400001'
file:
- access_level: open_access
  checksum: 8b3585df45b25091fba9bee9854b7d01
  content_type: application/pdf
  creator: dernst
  date_created: 2025-06-24T06:33:30Z
  date_updated: 2025-06-24T06:33:30Z
  file_id: '19887'
  file_name: 2025_EuropJournCombinatorics_Dvorak.pdf
  file_size: 564203
  relation: main_file
  success: 1
file_date_updated: 2025-06-24T06:33:30Z
has_accepted_license: '1'
intvolume: '       127'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
publication: European Journal of Combinatorics
publication_identifier:
  issn:
  - 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Precoloring extension in planar near-Eulerian-triangulations
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 127
year: '2025'
...