Let $G$ be a simple cubic graph (that is, 3-regular). A *dominating circuit* of $G$ is a circuit $C$ such that each edge of $G$ has an endvertex in $C$. The circuit $C$ is *chordless* if no edge which is not in $C$ has both endvertices in $C$ (such edges are called *chords* of $C$). An {\it MO graph} is a simple cubic graph which has a chordless dominating circuit, and (UPDATED EDIT) in addition, two edges incident with a vertex not in the dominating circuit cannot be attached to consecutive vertices in the dominating circuit. 


QUESTION 1: Are MO graphs edge-3-colorable?


QUESTION 2: Are MO graphs Hamiltonian? An affirmative answer to this question implies an affirmative answer to the first one.


Computer generated experiments with randomly generated MO graphs, with fairly sizable graphs and thousands of them, suggest that the answer to both questions is YES. I would hope that at least question 1 can be settled. Question 2 looks hard. I have tried graphs with up to 100 claws with the 3-vertex off the dominating circuit, so that is 400 vertices.


A related question is the following:


QUESTION 3: What cubic Hamiltonian graphs with a Hamiltonian circuit $C$ have Hamiltonian circuits that contain all chords of $C$ in the same Hamiltonian circuit? Is there an effective characterization of these? Such a characterization would maybe allow one to settle question 2.



Edge colorability and Hamiltonicity of certain classes of cubic graphs (MO graphs)
This is a NEW EDITION using the condition that two edges incident with a vertex not in the dominating circuit cannot be attached to consecutive vertices in the dominating circuit.


I tried 200 million at random for each size $8, 12, \ldots, 48$ (it must be a multiple of 4). They were all hamiltonian except for 4 graphs on 28 vertices and 1 graph on 40 vertices.


Vertices $0,1,\ldots,3n/4-1$ in natural order are the dominating cycle. The neighbours of the other vertices are as follows.


**Graph 28-1.**
 21 : 1 6 8;
 22 : 16 18 20;
 23 : 5 7 9;
 24 : 4 17 19;
 25 : 2 12 14;
 26 : 0 3 10;
 27 : 11 13 15;


**Graph 28-2.**
 21 : 1 3 5;
 22 : 13 15 17;
 23 : 9 14 16;
 24 : 7 12 20;
 25 : 0 2 4;
 26 : 6 10 19;
 27 : 8 11 18;


**Graph 28-3.**
 21 : 2 4 6;
 22 : 10 12 17;
 23 : 0 8 15;
 24 : 1 3 5;
 25 : 9 14 19;
 26 : 11 16 18;
 27 : 7 13 20;


**Graph 28-4.**
 21 : 3 17 19;
 22 : 4 18 20;
 23 : 1 5 16;
 24 : 2 6 14;
 25 : 8 10 12;
 26 : 9 11 13;
 27 : 0 7 15;


**Graph 40-1.**
 30 : 0 24 27;
 31 : 1 25 28;
 32 : 7 14 17;
 33 : 4 6 23;
 34 : 8 10 12;
 35 : 9 11 16;
 36 : 2 15 26;
 37 : 18 20 22;
 38 : 13 19 21;
 39 : 3 5 29;


These have *not* been tested for 3-edge-colourability.


I am confident that there are many non-hamiltonian examples on larger sizes, but searching randomly quickly becomes a very inefficient way to find them.


