Pith. sign in

REVIEW

3-Coloring $C_4$ or $C_3$-free Diameter Two Graphs

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2307.15036 v1 pith:HV7G62L3 submitted 2023-07-27 cs.DS cs.DMmath.CO

classification cs.DScs.DMmath.CO
keywords freegraphsproblempolynomial-timecoloringdiametergraphsolvable
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

The question of whether 3-Coloring can be solved in polynomial-time for the diameter two graphs is a well-known open problem in the area of algorithmic graph theory. We study the problem restricted to graph classes that avoid cycles of given lengths as induced subgraphs. Martin et. al. [CIAC 2021] showed that the problem is polynomial-time solvable for $C_5$-free or $C_6$-free graphs, and, $(C_4,C_s)$-free graphs where $s \in \{3,7,8,9\}$. We extend their result proving that it is polynomial-time solvable for $(C_4,C_s)$-free graphs, for any constant $s$, and for $(C_3,C_7)$-free graphs. Our results also hold for the more general problem List 3-Colouring.

Discussion (0). Continue with ORCID to comment.

Pith tools