This HTML5 document contains 47 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
n10http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
n15https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
n13http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Degeneracy_(graph_theory)
dbo:wikiPageWikiLink
dbr:Cereceda's_conjecture
Subject Item
dbr:Reconfiguration
dbo:wikiPageWikiLink
dbr:Cereceda's_conjecture
Subject Item
dbr:Cereceda's_conjecture
rdfs:label
Cereceda's conjecture
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.
foaf:depiction
n13:Path_3-colorings.svg
dcterms:subject
dbc:Reconfiguration dbc:Graph_coloring dbc:Conjectures
dbo:wikiPageID
62405866
dbo:wikiPageRevisionID
1032192508
dbo:wikiPageWikiLink
dbr:Complete_graph dbr:Discrete_uniform_distribution dbr:Tree_(graph_theory) n10:Path_3-colorings.svg dbr:Reconfiguration dbr:Random_walk dbr:Big_O_notation dbr:Sparse_graph dbr:Degeneracy_(graph_theory) dbr:Glauber_dynamics dbc:Graph_coloring dbr:Diameter dbr:Greedy_coloring dbr:Steady_state dbr:Cycle_graph dbc:Conjectures dbr:Kempe_chain dbr:Linear_time dbr:Path_graph dbr:Markov_chain_mixing_time dbc:Reconfiguration dbr:Graph_coloring
owl:sameAs
wikidata:Q85751315 n15:C7Bws
dbp:wikiPageUsesTemplate
dbt:Math dbt:R dbt:Reflist dbt:Harvtxt dbt:Unsolved dbt:Mvar
dbo:thumbnail
n13:Path_3-colorings.svg?width=300
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.
prov:wasDerivedFrom
wikipedia-en:Cereceda's_conjecture?oldid=1032192508&ns=0
dbo:wikiPageLength
10189
foaf:isPrimaryTopicOf
wikipedia-en:Cereceda's_conjecture
Subject Item
dbr:List_of_unsolved_problems_in_mathematics
dbo:wikiPageWikiLink
dbr:Cereceda's_conjecture
Subject Item
wikipedia-en:Cereceda's_conjecture
foaf:primaryTopic
dbr:Cereceda's_conjecture