TR-2016-12

An algorithm for identifying cycle-plus-triangles graphs

Kristóf Bérczi, Yusuke Kobayashi



Abstract

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:

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


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