Showing cs.DMShow all
3 papers · 1 filter
cs.DM2018
Connected greedy colouring in claw-free graphs
Ngoc Khang Le, Nicolas Trotignon
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 c…
cs.DM2018
Coloring even-hole-free graphs with no star cutset
Ngoc Khang Le
A \emph{hole} is a chordless cycle of length at least . A graph is \emph{even-hole-free} if it does not contain any hole of even length as an induced subgraph. In this paper, we…
cs.DM2017
Detecting induced subdivision of
Ngoc Khang Le
In this paper, we propose a polynomial-time algorithm to test whether a given graph contains a subdivision of as an induced subgraph.