PreprintarXiv licencearXiv
Deciding lettericity is NP-complete, even for four-colorable comparability graphs
Abstract
We prove that deciding whether a graph has lettericity at most k is NP-complete, even for four-colorable comparability graphs. Our reduction maps a bipartite graph G to the graph obtained from its incidence graph by inflating each vertex by a clique or an independent set of three vertices. The lettericity of this graph is determined by the numbers of vertices and edges of G and the greatest number of edge-disjoint paths on four vertices in G. Teypaz and Rapine showed that deciding whether the edges of a bipartite graph can be partitioned into paths on four vertices is NP-complete.
Related
- On uniquely colorable Cayley graphs
- Deciding monotonicity of simple drawings of the complete graph
- Biplanar graphs with independence number two are 9-colorable
- Coloring 3-colorable graphs with O(n4/23) colors via a Gaussian-cover recursion
- Strong complete immersions in graphs with independence number two
BibTeX
@misc{vatter2026deciding,
title = {{Deciding lettericity is NP-complete, even for four-colorable comparability graphs}},
author = {Vincent Vatter},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06482},
eprint = {2610.06482},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06482},
}
RIS
TY - UNPB
TI - Deciding lettericity is NP-complete, even for four-colorable comparability graphs
AU - Vincent Vatter
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06482
UR - https://arxiv.org/abs/2610.06482
AB - We prove that deciding whether a graph has lettericity at most k is NP-complete, even for four-colorable comparability graphs. Our reduction maps a bipartite graph G to the graph obtained from its incidence graph by inflating each vertex by a clique or an independent set of three vertices. The lettericity of this graph is determined by the numbers of vertices and edges of G and the greatest number of edge-disjoint paths on four vertices in G. Teypaz and Rapine showed that deciding whether the edges of a bipartite graph can be partitioned into paths on four vertices is NP-complete.
ER -