Note on incidence chromatic number of subquartic graphs (Q2410036): Difference between revisions

An incidence in a graph is a pair \((v,e)\), where \(v\) is an end-vertex of \(e\). Two incidences \((u,e)\) and \((v,f)\) are adjacent if \(u=v\), \(e=f\) or \(vu \in \{e,f\}\). An incidence colouring of a graph is a colouring of its incidences so that adjacent incidencies receive different colours. The incidence chromatic number \(\chi_i(G)\) of a graph \(G\) is the fewest number of colours required by an incidence colouring. \textit{R. A. Brualdi} and \textit{J. J. Q. Massey} [Discrete Math. 122, No. 1--3, 51--58 (1993; Zbl 0790.05026)] conjectured that \(\chi_i(G) \leq \Delta(G)+2\), where as usual \(\Delta(G)\) denotes the maximum degree of \(G\). Although this conjecture has been disproved in general, it has been established in several special cases, in particular for subcubic graphs by \textit{M. Maydanskiy} [ibid. 292, No. 1--3, 131--141 (2005; Zbl 1059.05051)] In the present paper, the authors establish Brualdi and Massey's conjecture [loc. cit.] for graphs with maximum degree 4. The proof works by first taking a graph with maximum degree 4, removing the edges of a maximum matching and then those of a second matching covering all the remaining vertices of degree 4. The resulting graph is subcubic and its incidences may be coloured with 5 colours. A fairly complicated recolouring procedure redistributes the coloured incidences in the original graph in such a way that the remaining incidences may be coloured with just two more colours.