Connected sequential colourings
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.
- A note on strong perfectness of graphs
- scientific article; zbMATH DE number 3889564 (Why is no real title available?)
- scientific article; zbMATH DE number 3891424 (Why is no real title available?)
- scientific article; zbMATH DE number 3891425 (Why is no real title available?)
- scientific article; zbMATH DE number 3522018 (Why is no real title available?)
- Sequential coloring versus Welsh-Powell bound
- Hard-to-color graphs for connected sequential colorings
- The connected greedy coloring game
- The canonical coloring graphs of trees and cycles
- Coloring Meyniel graphs in linear time
- Connected greedy colourings
- Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
- Connected greedy coloring of H-free graphs
- Connecting colored point sets
This page was built for publication: Connected sequential colourings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1123198)