2-distance 4-coloring of planar subcubic graphs with girth at least 21

A $2$-distance $k$-coloring of a graph is a proper vertex $k$-coloring where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$-distance $4$-coloring for planar subcubic graphs with girth at least 21. We also show a construction of a planar subcubic graph of girth 11 that is not $2$-distance $4$-colorable. Comment: 21 pages, 14 figures

Authors

Publication Details

Journal
Discrete Mathematics & Theoretical Computer Science
Published
2025-03-05
DOI
https://doi.org/10.46298/dmtcs.7563
Citations
1
Primary Topic
graph theory and CDMA systems
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

2-distance 4-coloring of planar subcubic graphs with girth at least 21

Mickaël Montassier, Hoang La
1 citations
Discrete Mathematics & Theoretical Computer Science
graph theory and CDMA systems
article

2-distance 4-coloring of planar subcubic graphs with girth at least 21

Mickaël Montassier, Hoang La
article en
1 citations

Abstract

A $2$-distance $k$-coloring of a graph is a proper vertex $k$-coloring where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$-distance $4$-coloring for planar subcubic graphs with girth at least 21. We also show a construction of a planar subcubic graph of girth 11 that is not $2$-distance $4$-colorable. Comment: 21 pages, 14 figures

Discrete Mathematics & Theoretical Computer ScienceVol. vol. 26:3(Graph Theory)
Openalex Percentile: Top 100%
graph theory and CDMA systems
DOIOpen Access PDFOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

2-distance 4-coloring of planar subcubic graphs with girth at least 21 — Mickaël Montassier, Hoang La · Discrete Mathematics & Theoretical Computer Science (2025) | TGRS Research Map | TGRS