pith. sign in

arxiv: 2606.21534 · v1 · pith:GMLTBMZ3new · submitted 2026-06-19 · 🧮 math.CO · cs.CC

Conformability is NP-complete, even on connected regular graphs

J\'ozsef Pint\'er This is my paper

Pith reviewed 2026-06-26 13:40 UTC · model grok-4.3

classification 🧮 math.CO cs.CC
keywords conformabilityNP-completenessregular graphsgraph coloringtriangle packingcomputational complexityindependence numberclique number
0
0 comments X

The pith

Deciding whether a graph is conformable is NP-complete even for connected regular graphs of odd order.

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

The paper proves that deciding conformability is NP-complete. Conformability requires a proper coloring with Delta plus one colors such that the number of color classes whose size has the wrong parity relative to the graph order is at most the sum over vertices of Delta minus degree. The hardness holds for the restricted class of connected regular graphs of odd order whose independence number is three and whose maximum degree is at least half the number of vertices. The proof reduces from the problem of deciding whether a graph of clique number three has a perfect triangle packing, by first regularizing the graph and then taking its complement so that the allowed color classes become exactly the singletons and triangles whose total count is fixed by the number of colors.

Core claim

We settle the general problem by proving that Conformability is NP-complete. Hardness holds even for connected regular graphs G of odd order with independence number α(G)=3 and maximum degree Δ(G)≥|V(G)|/2. In particular, NP-completeness persists when every color class is forced to have the parity of the order. The reduction starts from perfect triangle packing in graphs of clique number three, regularizes the source graph while preserving the relevant triangle packings, and then takes the complement. In the complement, conformable color classes correspond to odd cliques of the regularized graph; K4-freeness restricts these cliques to singletons or triangles, and the number of available colo

What carries the argument

Reduction from perfect triangle packing on K4-free graphs via regularization followed by complementation, under which conformable color classes in the resulting regular graph correspond exactly to selections of singletons and triangles.

If this is right

  • No polynomial-time algorithm for conformability exists on the stated graph class unless P equals NP.
  • The parity-matching requirement on every color class does not make the decision problem polynomial-time solvable.
  • Hardness continues to hold when the maximum degree is at least half the order and the graph is connected and regular.
  • The same reduction technique shows that the problem remains NP-complete when color classes are forced to match the parity of the graph order.

Where Pith is reading between the lines

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

  • The same regularization-plus-complement technique may establish NP-completeness for other parity-constrained coloring problems on regular graphs.
  • One could test whether the hardness persists when the independence number is fixed at any constant greater than three.
  • The explicit bijection between color classes and triangle packings suggests that approximation versions of conformability might be studied via known triangle-packing approximability results.

Load-bearing premise

Regularization of the input graphs preserves the exact set of triangle packings while the subsequent complement maps conformable colorings onto selections of singletons and triangles whose count is dictated by the number of colors.

What would settle it

A connected regular graph of odd order with independence number three that admits a conformable (Delta plus one)-coloring yet whose preimage under the regularization-and-complement map has no perfect triangle packing would falsify the reduction.

read the original abstract

A graph $G$ is conformable if it admits a proper $(\Delta(G)+1)$-coloring in which, among the $\Delta(G)+1$ color classes including the empty ones, at most $\sum_{v\in V(G)}(\Delta(G)-d_G(v))$ have parity different from that of $|V(G)|$. The complexity of deciding conformability was left open in recent work, and positive results for several graph classes had suggested that the problem might be polynomial-time solvable. We settle the general problem by proving that Conformability is NP-complete. Hardness holds even for connected regular graphs $G$ of odd order with independence number $\alpha(G)=3$ and maximum degree $\Delta(G)\ge |V(G)|/2$. In particular, NP-completeness persists when every color class is forced to have the parity of the order. The reduction starts from perfect triangle packing in graphs of clique number three, regularizes the source graph while preserving the relevant triangle packings, and then takes the complement. In the complement, conformable color classes correspond to odd cliques of the regularized graph; $K_4$-freeness restricts these cliques to singletons or triangles, and the number of available colors forces exactly the required number of disjoint triangles.

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 / 1 minor

Summary. The paper proves that Conformability is NP-complete, even restricted to connected regular graphs G of odd order with α(G)=3 and Δ(G)≥|V(G)|/2. The proof reduces from perfect triangle packing on graphs with clique number 3: the source graph is regularized (preserving relevant triangle packings while ensuring connectivity, regularity, odd order, and α=3), the complement is taken, and conformable (Δ+1)-colorings in the complement are shown to correspond exactly to selections of singletons plus the precise number of triangles required by the color count, with K4-freeness restricting larger cliques.

Significance. If the reduction holds, the result resolves the open complexity status of conformability and establishes hardness in a narrow, highly structured class (including the parity-forcing condition on color classes). This strengthens earlier positive results on special graph families and provides a template for hardness proofs via regularization-plus-complementation.

major comments (2)
  1. [reduction description] Reduction (abstract and reduction paragraph): The regularization construction must be shown to preserve perfect triangle packings in both directions without introducing extraneous triangles. The manuscript needs an explicit argument that added vertices/edges neither create new triangles usable in a packing nor destroy existing ones from the ω=3 source, while simultaneously producing a connected regular graph of odd order with α=3 and Δ≥n/2. This equivalence is load-bearing for the Karp reduction.
  2. [reduction description] Complement step (abstract): After regularization, the resulting graph must remain K4-free so that the only possible cliques in the complement are singletons and triangles. The manuscript must verify that the regularization does not introduce K4s (or larger cliques) that would allow non-triangle color classes in the conformable coloring, breaking the exact correspondence with perfect triangle packings.
minor comments (1)
  1. [reduction description] The construction of the regularization (vertex/edge additions) would benefit from a formal, numbered definition or diagram rather than a prose description alone.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments correctly identify places where the reduction requires more explicit verification to be fully rigorous. We will revise the manuscript to supply these arguments in detail.

read point-by-point responses

  1. Referee: Reduction (abstract and reduction paragraph): The regularization construction must be shown to preserve perfect triangle packings in both directions without introducing extraneous triangles. The manuscript needs an explicit argument that added vertices/edges neither create new triangles usable in a packing nor destroy existing ones from the ω=3 source, while simultaneously producing a connected regular graph of odd order with α=3 and Δ≥n/2. This equivalence is load-bearing for the Karp reduction.

    Authors: We agree that an explicit bidirectional preservation argument is required. The current text asserts preservation but does not supply the full details. In the revised manuscript we will insert a dedicated lemma proving: (1) every perfect triangle packing of the source extends to the regularized graph without using newly created triangles, (2) every perfect triangle packing of the regularized graph restricts to one in the source, and (3) the construction simultaneously yields a connected regular graph of odd order with α=3 and Δ≥n/2. The proof will enumerate the added vertices/edges and show they contribute neither new triangles nor destroy existing ones. revision: yes

  2. Referee: Complement step (abstract): After regularization, the resulting graph must remain K4-free so that the only possible cliques in the complement are singletons and triangles. The manuscript must verify that the regularization does not introduce K4s (or larger cliques) that would allow non-triangle color classes in the conformable coloring, breaking the exact correspondence with perfect triangle packings.

    Authors: We acknowledge that K4-freeness after regularization is essential for the exact correspondence. Although the source graphs satisfy ω=3 and the regularization is constructed to avoid larger cliques, the manuscript does not contain an explicit verification. The revision will add a short argument (or sub-lemma) showing that none of the added edges or vertices create a K4; this will be placed immediately before the complement step so that the restriction of color classes to singletons and triangles is rigorously justified. revision: yes

Circularity Check

0 steps flagged

No circularity; standard Karp reduction from independent source problem

full rationale

The derivation is a reduction from perfect triangle packing (an externally defined NP-complete problem on ω=3 graphs) to conformability. The regularization and complement steps construct the target instance; they do not define the target result in terms of itself or rename fitted parameters as predictions. No equations or self-citation chains reduce the NP-completeness claim to its own inputs by construction. The source problem and the reduction correctness are independent of the present paper's fitted values or prior self-citations.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the NP-completeness of perfect triangle packing in clique-number-3 graphs (a domain assumption from prior literature) together with the correctness of the two-step reduction; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Perfect triangle packing remains NP-complete when restricted to graphs with clique number three.
    The reduction begins from this problem; its hardness is taken as given from earlier results.

pith-pipeline@v0.9.1-grok · 5755 in / 1295 out tokens · 33676 ms · 2026-06-26T13:40:07.364705+00:00 · methodology

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

18 extracted references · 14 canonical work pages

  1. [1]

    A. G. Chetwynd and A. J. W. Hilton. Some refinements of the total chromatic number conjecture.Congressus Numerantium 66, pages 195– 216, 1988

    1988

  2. [2]

    A. G. Chetwynd, A. J. W. Hilton, and C. Zhao. The Total Chromatic Number of Graphs of High Minimum Degree.Journal of the London Mathematical Society, 1991.doi:10.1112/jlms/s2-44.2.193. 13

    work page doi:10.1112/jlms/s2-44.2.193 1991

  3. [3]

    K. H. Chew. Total chromatic number of regular graphs of odd order and high degree.Discrete Mathematics, 154(1):41–51, June 1996.doi: 10.1016/0012-365X(95)00034-T

    work page doi:10.1016/0012-365x(95)00034-t 1996

  4. [4]

    Faria, M

    L. Faria, M. Nigro, M. Preissmann, and D. Sasaki. Results about the total chromatic number and the conformability of some families of circulant graphs.Discrete Applied Mathematics, 340:123–133, Dec. 2023. doi:10.1016/j.dam.2023.07.003

    work page doi:10.1016/j.dam.2023.07.003 2023

  5. [5]

    Faria, M

    L. Faria, M. Nigro, and D. Sasaki. On the conformability of regular line graphs.RAIRO - Operations Research, 57(5):2527–2536, Sept. 2023. doi:10.1051/ro/2023140

    work page doi:10.1051/ro/2023140 2023

  6. [6]

    Crossley and Y

    L. Faria, M. Nigro, and D. Sasaki. A polynomial-time algorithm for con- formable coloring on regular bipartite and subcubic graphs.Discrete Opti- mization, 55:100865, Feb. 2025.doi:10.1016/j.disopt.2024.100865

    work page doi:10.1016/j.disopt.2024.100865 2025

  7. [7]

    Faria, M

    L. Faria, M. Nigro, and D. Sasaki. Strong conformable coloring: the conformable coloring for Type 1 graphs.Procedia Computer Science, 273:405–412, 2025.doi:10.1016/j.procs.2025.10.325

    work page doi:10.1016/j.procs.2025.10.325 2025

  8. [8]

    M. R. Garey and D. S. Johnson.Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, 1979

    1979

  9. [9]

    Guruswami, C

    V. Guruswami, C. P. Rangan, M. S. Chang, G. J. Chang, and C. K. Wong. The Vertex-Disjoint Triangles Problem. In J. Hromkovič and O. Sýkora, editors,Graph-Theoretic Concepts in Computer Science, pages 26–37, Berlin, Heidelberg, 1998. Springer.doi:10.1007/10692760_3

    work page doi:10.1007/10692760_3 1998

  10. [10]

    Hajnal and E

    A. Hajnal and E. Szemerédi. Proof of a conjecture of P. Erdős. In P. Erdős, A. Rényi, and V. T. Sós, editors,Combinatorial Theory and Its Applications, II, volume 4 ofColloquia Mathematica Societatis János Bolyai, pages 601–623. North-Holland, Amsterdam, 1970

    1970

  11. [11]

    Hamilton, A

    G. Hamilton, A. Hilton, and H. Hind. Totally Critical Even Order Graphs.Journal of Combinatorial Theory, Series B, 76(2):262–279, July 1999.doi:10.1006/jctb.1999.1902

    work page doi:10.1006/jctb.1999.1902 1999

  12. [12]

    A. J. W. Hilton and H. R. Hind. Non-conformable subgraphs of non- conformable graphs.Discrete Mathematics, 256(1):203–224, 2002.doi: 10.1016/S0012-365X(01)00433-2. 14

    work page doi:10.1016/s0012-365x(01)00433-2 2002

  13. [13]

    A. J. W. Hilton, F. C. Holroyd, and C. Zhao. The Overfull Conjecture and the Conformability Conjecture.Discrete Mathematics, 241(1):343–361, Oct. 2001.doi:10.1016/S0012-365X(01)00153-4

    work page doi:10.1016/s0012-365x(01)00153-4 2001

  14. [14]

    J. E. Hopcroft and R. M. Karp. An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs.SIAM Journal on Computing, 2(4):225– 231, Dec. 1973.doi:10.1137/0202019

    work page doi:10.1137/0202019 1973

  15. [15]

    H. A. Kierstead, A. V. Kostochka, M. Mydlarz, and E. Szemerédi. A fast algorithm for equitable coloring.Combinatorica, 30(2):217–224, Mar. 2010.doi:10.1007/s00493-010-2483-5

    work page doi:10.1007/s00493-010-2483-5 2010

  16. [16]

    C. J. H. McDiarmid and A. Sánchez-Arroyo. Total colouring regular bipartite graphs is NP-hard.Discrete Mathematics, 124(1):155–162, Jan. 1994.doi:10.1016/0012-365X(92)00058-Y

    work page doi:10.1016/0012-365x(92)00058-y 1994

  17. [17]

    Sánchez-Arroyo

    A. Sánchez-Arroyo. Determining the total colouring number is np- hard.Discrete Mathematics, 78(3):315–319, Jan. 1989.doi:10.1016/ 0012-365X(89)90187-8

    1989

  18. [18]

    Zorzi, C

    A. Zorzi, C. M. H. Figueiredo, R. C. S. Machado, L. M. Zatesko, and U. S. Souza. Compositions, decompositions, and conformability for total coloring on power of cycle graphs.Discrete Applied Mathematics, 323:349–363, Dec. 2022.doi:10.1016/j.dam.2021.06.012. 15

    work page doi:10.1016/j.dam.2021.06.012 2022