Circle graphs and the cycle double cover conjecture |
| |
Authors: | François Genest |
| |
Institution: | Department of Computer Science and Software Engineering, Concordia University, 1455, de Maisonneuve blvd West, Montréal, Québec, H3G 1M8, Canada |
| |
Abstract: | The long standing Cycle Double Cover Conjecture states that every bridgeless graph can be covered by a family of cycles such that every edge is covered exactly twice. Intimately related is the problem of finding, in an eulerian graph, a circuit decomposition compatible with a given transition system (transition systems are also known as decompositions into closed paths). One approach that seems promising consists in finding a black anticlique in the corresponding Sabidussi orbit of bicolored circle graphs. |
| |
Keywords: | Circle graph Compatibility conjecture Cycle double cover Local complementation Transition system Interlace polynomial |
本文献已被 ScienceDirect 等数据库收录! |
|