Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9514522 | Electronic Notes in Discrete Mathematics | 2005 | 4 Pages |
Abstract
A Meyniel graph is a graph in which every odd cycle of length at least five has two chords. We present a linear-time algorithm that colors optimally the vertices of a Meyniel graph and finds a clique of maximum size.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Benjamin Lévêque, Frédéric Maffray,