Title of article :
Colouring of cubic graphs by Steiner triple systems
Author/Authors :
Holroyd، نويسنده , , Fred and ?koviera، نويسنده , , Martin، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2004
Pages :
10
From page :
57
To page :
66
Abstract :
Let S be a Steiner triple system and G a cubic graph. We say that G is S-colourable if its edges can be coloured so that at each vertex the incident colours form a triple of S. We show that if S is a projective system PG(n,2), n⩾2, then G is S-colourable if and only if it is bridgeless, and that every bridgeless cubic graph has an S-colouring for every Steiner triple system of order greater than 3. We establish a condition on a cubic graph with a bridge which ensures that it fails to have an S-colouring if S is an affine system, and we conjecture that this is the only obstruction to colouring any cubic graph with any non-projective system of order greater than 3.
Journal title :
Journal of Combinatorial Theory Series B
Serial Year :
2004
Journal title :
Journal of Combinatorial Theory Series B
Record number :
1527407
Link To Document :
بازگشت