3 papers
cs.DM2011
A polynomial 3-colorability algorithm with automatic generation of NO 3-colorability (i.e. Co-NP) short proofs
Jose Antonio Martin H
In this paper, an algorithm for determining 3-colorability, i.e. the decision problem (YES/NO), in planar graphs is presented. The algorithm, although not exact (it could produce f…
math.CO2010
Upper-critical graphs
Jose Antonio Martin H
This work introduces the concept of \emph{upper-critical graphs}, in a complementary way of the conventional (lower)critical graphs: an element of a graph is called \emph{c…
math.CO2009
Graph-Chromatic Implicit Relations
Jose Antonio Martin H
A theory about the implication structure in graph coloring is presented. Discovering hidden relations is a crucial activity in every scientific discipline. The development of mathe…