An algorithm for identifying cycle-plus-triangles graphs

Kristóf Bérczi, Yusuke Kobayashi


The union of $n$ node-disjoint triangles and a Hamiltonian cycle on the same node set is called a cycle-plus-triangles graph. Du, Hsu and Hwang conjectured that every such graph has independence number $n$. The conjecture was later strengthened by Erdos claiming that every cycle-plus-triangles graph has a $3$-colouring, which was verified by Fleischner and Stiebitz using the Combinatorial Nullstellensatz. An elementary proof was later given by Sachs. However, these proofs are non-algorithmic and the complexity of finding a proper $3$-colouring is left open.
As a first step toward an algorithm, we show that it can be decided in polynomial time whether a graph is a cycle-plus-triangles graph. Our algorithm is based on revealing structural properties of cycle-plus-triangles graphs. We hope that these observations may also help to find a proper $3$-colouring in polynomial time.

Bibtex entry:

AUTHOR = {B{\'e}rczi, Krist{\'o}f and Kobayashi, Yusuke},
TITLE = {An algorithm for identifying cycle-plus-triangles graphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2016},
NUMBER = {TR-2016-12}

Last modification: 13.3.2018. Please email your comments to Tamás Király!