About: Cereceda's conjecture

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In the mathematics of graph coloring, Cereceda’s conjecture is an unsolved problem on the distance between pairs of colorings of sparse graphs. It states that, for two different colorings of a graph of degeneracy d, both using at most d + 2 colors, it should be possible to reconfigure one coloring into the other by changing the color of one vertex at a time, using a number of steps that is quadratic in the size of the graph. The conjecture is named after Luis Cereceda, who formulated it in his 2007 doctoral dissertation.

thumbnail
Property Value
dbo:abstract
  • In the mathematics of graph coloring, Cereceda’s conjecture is an unsolved problem on the distance between pairs of colorings of sparse graphs. It states that, for two different colorings of a graph of degeneracy d, both using at most d + 2 colors, it should be possible to reconfigure one coloring into the other by changing the color of one vertex at a time, using a number of steps that is quadratic in the size of the graph. The conjecture is named after Luis Cereceda, who formulated it in his 2007 doctoral dissertation. (en)
dbo:thumbnail
dbo:wikiPageID
  • 62405866 (xsd:integer)
dbo:wikiPageLength
  • 10189 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1032192508 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • In the mathematics of graph coloring, Cereceda’s conjecture is an unsolved problem on the distance between pairs of colorings of sparse graphs. It states that, for two different colorings of a graph of degeneracy d, both using at most d + 2 colors, it should be possible to reconfigure one coloring into the other by changing the color of one vertex at a time, using a number of steps that is quadratic in the size of the graph. The conjecture is named after Luis Cereceda, who formulated it in his 2007 doctoral dissertation. (en)
rdfs:label
  • Cereceda's conjecture (en)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License