pith. sign in

arxiv: 1805.01953 · v1 · pith:X3MNQ7MXnew · submitted 2018-05-04 · 💻 cs.DM · math.CO

Connected greedy colouring in claw-free graphs

classification 💻 cs.DM math.CO
keywords connectedcolouringeverygraphgreedyorderalgorithmclaw-free
0
0 comments X
read the original abstract

An ordering of the vertices of a graph is \emph{connected} if every vertex (but the first) has a neighbor among its predecessors. The greedy colouring algorithm of a graph with a connected order consists in taking the vertices in order, and assigning to each vertex the smallest available colour. A graph is \emph{good} if the greedy algorithm on every connected order gives every connected induced subgraph of it an optimal colouring. We give the characterization of good claw-free graphs in terms of minimal forbidden induced subgraphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.