Oleg Borodin and André Raspaud
"A sufficient condition for planar graphs to be 3-colorable"
Journal of Combinatorial Theory B88, 2003, 17–27

state the following conjecture:

Conjecture 1.2:
Every planar graph without adjacent 3-cycles and 5-cycles is 3-colorable.

My question is whether it is possible to describe this condition of "non-adjacent 3-cycles" purely in terms of the cubic adjacency matrix?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.