pith. sign in

arxiv: 2606.30282 · v2 · pith:IA5NX554new · submitted 2026-06-29 · 🧮 math.CO · cs.DM

List 3-coloring C₄-free graphs of diameter-2 in polynomial-time

Yukihiro Murakami This is my paper

Pith reviewed 2026-07-03 22:36 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords list 3-coloringC4-free graphsdiameter 2polynomial-time algorithmstructural characterization3-colorabilitygraph algorithms
0
0 comments X

The pith

List 3-coloring of C4-free diameter-2 graphs admits a polynomial-time algorithm.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that list 3-coloring can be performed in polynomial time on C4-free graphs with diameter exactly 2. It does so by first proving a structural fact that rules out 3-colorability for a large subclass of these graphs: those without a vertex adjacent to every other vertex when the maximum degree is at least 17. A reader would care because the result converts an apparently hard coloring task into an efficiently decidable one on this concrete graph family, separating it from general graph coloring.

Core claim

We show that list 3-coloring a C4-free graph of diameter 2 can be done in polynomial time. Our algorithm is based on a structural characterization showing that many such graphs are not 3-colorable. In particular, we show that C4-free graphs of diameter 2 without universal vertices, where the maximum degree is at least 17, are not 3-colorable.

What carries the argument

The structural characterization that proves non-3-colorability of C4-free diameter-2 graphs without universal vertices when maximum degree is at least 17; this characterization reduces the coloring instances to cases the algorithm can solve directly.

If this is right

  • The list-3-coloring decision problem on this graph class becomes solvable in polynomial time.
  • Any C4-free diameter-2 graph without a universal vertex and with maximum degree at least 17 is immediately rejected as not 3-colorable.
  • The algorithm can focus computational effort on the remaining cases that contain universal vertices or have smaller maximum degree.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same non-colorability threshold might be used to derive bounds on the chromatic number of related diameter-2 graph families.
  • Refinements of the degree-17 cutoff could produce tighter structural theorems for the same graphs.
  • The result suggests that forbidding C4 is the ingredient that makes diameter-2 coloring tractable, while its presence may restore hardness.

Load-bearing premise

C4-free graphs of diameter 2 that lack a universal vertex and have maximum degree at least 17 are never 3-colorable.

What would settle it

Exhibit one C4-free graph of diameter 2 with no universal vertex, maximum degree at least 17, together with a proper 3-coloring of its vertices.

Figures

Figures reproduced from arXiv: 2606.30282 by Yukihiro Murakami.

Figure 1
Figure 1. Figure 1: All C4-free graphs of diameter-2 when ∆ ≤ 3. Note that they are 3- colorable, which means they are potentially list 3-colorable. The three graphs on the left do not have universal vertices; the two graphs on the right do have universal vertices. 3 Characterizing C4-free graphs of diameter-2 We introduce notation which will be used in the rest of this paper. We write G = (V, E) to mean a C4-free graph of di… view at source ↗
Figure 2
Figure 2. Figure 2: A visualization of the lower bound |Vi | ≥ ∆−2 in the proof of Lemma 3.7, for the case when there are non-adjacent parts. The figure shows a subgraph of G[N2], illustrating how u ∈ Vi covers the vertices of a non-adjacent part Vj . The dot￾ted line between Vi and Vj indicate the non-adjacency. The additional vertices in V1, . . . , Vj−1, Vj+1, V∆ are omitted for clarity. 3.3 Classifying vertices in N2 Let … view at source ↗
Figure 3
Figure 3. Figure 3: A C4-free G of diameter-2 with maximum degree 4. (a) G without the edges in E(G[N2]). c1, c2, d1, d2 are Type-1 vertices, b1, b2 are Type-2 vertices, and a1, a2 are Type-3 vertices. (b) G[N2]. The dotted line between V1 and V2 indicates that the two parts are non-adjacent. In accordance with Lemma 3.14, b1, b2 are not contained in a C3. a1, c2, d2 forms a C3 as they are pairwise adjacent and none of the ve… view at source ↗
Figure 4
Figure 4. Figure 4: Diamond elimination (Rule 1) does not preserve induced [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
read the original abstract

We show that list $3$-coloring a~$C_4$-free graph of diameter-$2$ can be done in polynomial-time. Our algorithm is based on a structural characterization showing that many such graphs are not~$3$-colorable. In particular, we show that~$C_4$-free graphs of diameter-$2$ without universal vertices, where the maximum degree is at least~$17$, are not~$3$-colorable.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The manuscript claims a polynomial-time algorithm for list 3-coloring C_4-free graphs of diameter 2. The approach rests on a structural characterization that such graphs without universal vertices and with maximum degree at least 17 are not 3-colorable; the remaining cases (presence of a universal vertex or bounded degree) are asserted to reduce to list 2-coloring or brute-force enumeration.

Significance. A correct proof would constitute a notable positive result for list-coloring algorithms on a geometrically restricted graph class. The non-3-colorability statement, if established, would also be of independent combinatorial interest.

major comments (2)
  1. [Abstract] Abstract: the stated basis for the algorithm—that non-3-colorability of the high-degree, no-universal-vertex graphs supplies the rejection rule—is incorrect. A graph with χ(G) > 3 can still admit a proper list-3-coloring when the lists are drawn from a palette larger than three colors; the structural result therefore supplies no decision procedure for arbitrary list assignments in this case.
  2. [Abstract] Abstract: the claim that bounded-degree instances (Δ ≤ 16) are solvable by brute force requires an explicit size bound on n (e.g., n ≤ 1 + 16 + 16·15) together with a verification that the enumeration remains polynomial; without this, the reduction to the high-degree case is incomplete.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed report and the opportunity to respond. Below we address each major comment directly and indicate the revisions we will make.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the stated basis for the algorithm—that non-3-colorability of the high-degree, no-universal-vertex graphs supplies the rejection rule—is incorrect. A graph with χ(G) > 3 can still admit a proper list-3-coloring when the lists are drawn from a palette larger than three colors; the structural result therefore supplies no decision procedure for arbitrary list assignments in this case.

    Authors: We agree with the referee. Non-3-colorability of a graph does not rule out the existence of a list-3-coloring when the lists may be drawn from a larger palette, because a proper selection from the lists may employ more than three distinct colors overall. Consequently the structural characterization cannot function as a direct rejection rule for arbitrary list assignments. We will revise the abstract and the algorithmic description to remove this misstatement and to explain precisely how the structural result is combined with the other cases (universal vertices and bounded degree) to yield a correct decision procedure for list 3-coloring. revision: yes

  2. Referee: [Abstract] Abstract: the claim that bounded-degree instances (Δ ≤ 16) are solvable by brute force requires an explicit size bound on n (e.g., n ≤ 1 + 16 + 16·15) together with a verification that the enumeration remains polynomial; without this, the reduction to the high-degree case is incomplete.

    Authors: We agree that an explicit bound is required for the argument to be complete. In a graph of diameter 2 the number of vertices satisfies n ≤ 1 + Δ + Δ(Δ−1). Substituting Δ = 16 gives the constant bound n ≤ 257. Enumeration of all possible assignments from the given lists is therefore performed in constant time (at most 3^257 possibilities) and is polynomial. We will insert this explicit bound together with the verification into the revised manuscript. revision: yes

Circularity Check

0 steps flagged

No circularity; structural theorem is independent input to algorithm

full rationale

The provided abstract and description present the polynomial-time claim as following from a separately proven structural theorem on non-3-colorability of C4-free diameter-2 graphs without universal vertices and with Δ≥17. No equations, parameters, or self-citations are shown that would make any step self-definitional, a fitted input renamed as prediction, or dependent on a load-bearing self-citation chain. The derivation is therefore self-contained against external verification of the structural result.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no information on free parameters, axioms, or invented entities can be extracted from the provided text.

pith-pipeline@v0.9.1-grok · 5594 in / 1226 out tokens · 28210 ms · 2026-07-03T22:36:25.835013+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages · 1 internal anchor

  1. [1]

    Andries E. Brouwer. Hoffman-singleton graph.https://aeb.win.tue.nl/ graphs/Hoffman-Singleton.html. Accessed: 2026-06-05

    work page 2026

  2. [2]

    Four-coloring-free graphs

    Maria Chudnovsky, Sophie Spirkl, and Mingxian Zhong. Four-coloring-free graphs. i. extending an excellent precoloring.SIAM Journal on Computing, 53(1):111–145, 2024

    work page 2024

  3. [3]

    Faster 3-coloring of small- diameter graphs.SIAM Journal on Discrete Mathematics, 36(3):2205–2224, 2022

    Michał Dębski, Marta Piecyk, and Paweł Rzążewski. Faster 3-coloring of small- diameter graphs.SIAM Journal on Discrete Mathematics, 36(3):2205–2224, 2022

    work page 2022

  4. [4]

    The complexity of colouring problems on dense graphs.Theo- retical Computer Science, 43:337–343, 1986

    Keith Edwards. The complexity of colouring problems on dense graphs.Theo- retical Computer Science, 43:337–343, 1986

    work page 1986

  5. [5]

    A survey on the computational complexity of coloring graphs with forbidden subgraphs

    Petr A Golovach, Matthew Johnson, Daniël Paulusma, and Jian Song. A survey on the computational complexity of coloring graphs with forbidden subgraphs. Journal of Graph Theory, 84(4):331–363, 2017

    work page 2017

  6. [6]

    Faster 3-colouring algorithm for graphs of diameter 3

    Carla Groenland, Hidde Koerts, and Sophie Spirkl. Faster 3-colouring algorithm for graphs of diameter 3.arXiv preprint arXiv:2601.13072, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  7. [7]

    Hoffman’s ratio bound.Linear Algebra and its Applications, 617:215–219, 2021

    Willem H Haemers. Hoffman’s ratio bound.Linear Algebra and its Applications, 617:215–219, 2021

    work page 2021

  8. [8]

    On moore graphs with diameters 2 and 3.IBM Journal of Research and Development, 4(5):497–504, 1960

    Alan J Hoffman and Robert R Singleton. On moore graphs with diameters 2 and 3.IBM Journal of Research and Development, 4(5):497–504, 1960. 14

    work page 1960

  9. [9]

    3-coloringc4 orc 3-free diameter two graphs

    Tereza Klimošová and Vibha Sahlot. 3-coloringc4 orc 3-free diameter two graphs. InAlgorithms and Data Structures Symposium, pages 547–560. Springer, 2023

    work page 2023

  10. [10]

    Complex- ity of coloring graphs without forbidden induced subgraphs

    Daniel Král’, Jan Kratochvíl, Zsolt Tuza, and Gerhard J Woeginger. Complex- ity of coloring graphs without forbidden induced subgraphs. InInternational Workshop on Graph-Theoretic Concepts in Computer Science, pages 254–262. Springer, 2001

    work page 2001

  11. [11]

    Coverings and coloring of hypergraphs

    László Lovász. Coverings and coloring of hypergraphs. InProceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Comput- ing, volume 8 ofCongressus Numerantium, pages 3–12, Winnipeg, MB, 1973. Utilitas Mathematica Publishing

    work page 1973

  12. [12]

    Colouring h-free graphs of bounded diameter

    Barnaby Martin, Daniël Paulusma, and Siani Smith. Colouring h-free graphs of bounded diameter. In44th International Symposium on Mathematical Founda- tions of Computer Science (MFCS 2019), pages 14–1. Schloss Dagstuhl–Leibniz- Zentrum für Informatik, 2019

    work page 2019

  13. [13]

    Colouring generalized claw- free graphs and graphs of large girth: Bounding the diameter.Theoretical Com- puter Science, 931:104–116, 2022

    Barnaby Martin, Daniël Paulusma, and Siani Smith. Colouring generalized claw- free graphs and graphs of large girth: Bounding the diameter.Theoretical Com- puter Science, 931:104–116, 2022

    work page 2022

  14. [14]

    Colouring graphs of bounded diameter in the absence of small cycles.Discrete Applied Mathematics, 314:150–161, 2022

    Barnaby Martin, Daniël Paulusma, and Siani Smith. Colouring graphs of bounded diameter in the absence of small cycles.Discrete Applied Mathematics, 314:150–161, 2022

    work page 2022

  15. [15]

    Algorithms and almost tight results for 3-colorability of small diameter graphs.Algorithmica, 74(1):385–414, 2016

    George B Mertzios and Paul G Spirakis. Algorithms and almost tight results for 3-colorability of small diameter graphs.Algorithmica, 74(1):385–414, 2016

    work page 2016

  16. [16]

    Vertex colouring and forbidden subgraphs–a survey.Graphs and Combinatorics, 20(1):1–40, 2004

    Bert Randerath and Ingo Schiermeyer. Vertex colouring and forbidden subgraphs–a survey.Graphs and Combinatorics, 20(1):1–40, 2004

    work page 2004

  17. [17]

    Graph colorings with local constraints-a survey.Discussiones Math- ematicae Graph Theory, 17(2):161–228, 1997

    Zsolt Tuza. Graph colorings with local constraints-a survey.Discussiones Math- ematicae Graph Theory, 17(2):161–228, 1997. 15

    work page 1997