[PDF][PDF] The chromatic index of block intersection graphs of Kirkman triple systems and cyclic Steiner triple systems

IDDA Pike, J Poulin - AUSTRALASIAN JOURNAL OF …, 2017 - ajc.maths.uq.edu.au
IDDA Pike, J Poulin
AUSTRALASIAN JOURNAL OF COMBINATORICS, 2017ajc.maths.uq.edu.au
The block intersection graph of a combinatorial design with block set B is the graph with B as
its vertex set such that two vertices are adjacent if and only if their associated blocks are not
disjoint. The chromatic index of a graph G is the least number of colours that enable each
edge of G to be assigned a single colour such that adjacent edges never have the same
colour. A graph G for which the chromatic index equals the maximum degree is called Class
1; otherwise the chromatic index exceeds the maximum degree by one and G is called Class …
Abstract
The block intersection graph of a combinatorial design with block set B is the graph with B as its vertex set such that two vertices are adjacent if and only if their associated blocks are not disjoint. The chromatic index of a graph G is the least number of colours that enable each edge of G to be assigned a single colour such that adjacent edges never have the same colour. A graph G for which the chromatic index equals the maximum degree is called Class 1; otherwise the chromatic index exceeds the maximum degree by one and G is called Class 2. We conjecture that whenever a Steiner triple system has a block intersection graph with an even number vertices, the graph is Class 1. We prove this to be true for Kirkman triple systems and cyclic Steiner triple systems of order v≡ 9 (mod 12). We also prove that the conjecture holds for cyclic Steiner triple systems of order v≡ 1 (mod 12) for which ϕ (v) v-1⩾ 2 3
, where ϕ is Euler’s totient function.
ajc.maths.uq.edu.au
以上显示的是最相近的搜索结果。 查看全部搜索结果