Connected sequential colourings (Q1123198): Difference between revisions

A connected order in a connected graph \(G=(V,E)\) is any order \(v_ 1<...<v_ p\) such that \(\{v_ 1,...,v_ i\}\) induces a connected graph for any i with \(1\leq i\leq | V| =p\). A k-colouring of the nodes of G is called canonical if any node of any colour i is contained in a clique K of size i such that \(K\cap S_ j\neq \emptyset\) for \(1\leq j\leq i\). SCORE denotes an algorithm which scans the nodes of a connected graph in a connected order and gives to each node the smallest available colour. A class of graphs for which SCORE always produces optimal colourings is considered. It is proved that any connected order on any connected subgraph \(G'\) of G gives a canonical colouring of \(G'\) iff G is a parity graph without a forbidden graph on 6 nodes, where a parity graph is characterized by the property that every odd cycle of a length \(\geq 5\) has two crossing chords.