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

July 27, 2023 Β· Declared Dead Β· πŸ› Workshop on Algorithms and Data Structures

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Tereza KlimoΕ‘ovΓ‘, Vibha Sahlot arXiv ID 2307.15036 Category cs.DS: Data Structures & Algorithms Cross-listed cs.DM, math.CO Citations 2 Venue Workshop on Algorithms and Data Structures Last Checked 4 months ago
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.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted