Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities | Zendy

Ulrik Brandes | Zendy; Jürgen Lerner | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities

Author(s) -

Ulrik Brandes,

Jürgen Lerner

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-37791-3

DOI - 10.1007/11821069_18

Subject(s) - constant (computer programming) , bounded function , computer science , enhanced data rates for gsm evolution , random graph , graph coloring , colored , combinatorics , discrete mathematics , algorithm , mathematics , graph , theoretical computer science , artificial intelligence , mathematical analysis , materials science , composite material , programming language

Random 3-colorable graphs that are generated according to a G(n,p)-like model can be colored optimally, if p ≥c/n for some large constant c. However, these methods fail in a model where the edge-probabilities are non-uniform and not bounded away from zero. We present a spectral algorithm that succeeds in such situations.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research