|
Published in:
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 egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2016}, |
| NUMBER | = | {TR-2016-12} |