Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650792 | Discrete Mathematics | 2008 | 15 Pages |
Abstract
A semi-total colouring , μμ, of a graph G with maximum degree ΔΔ uses Δ+1Δ+1 colours and has the properties of a total colouring except that adjacent vertices need not have distinct colours. A beta edge is an edge v1v2v1v2 such that μ(v1)=μ(v2)μ(v1)=μ(v2). The beta parameter of G , β(G)β(G), is the minimum number of beta edges in any semi-total colouring of G.A critical edge of G is an edge whose deletion reduces the total chromatic number of G to Δ+1Δ+1. We derive the beta parameters of cycle and complete graphs; a quadratic bound for ββ in terms of ΔΔ for any graph with a critical edge; and a log-linear bound for any graph with a critical edge that is not contained in any triangle.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jini Williams, Fred Holroyd,