Publikation: Edge coloring lattice graphs
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
We develop the theory of the edge coloring of infinite lattice graphs, proving a necessary and sufficient condition for a proper edge coloring of a patch of a lattice graph to induce a proper edge coloring of the entire lattice graph by translation. This condition forms the cornerstone of a method that finds nearly minimal or minimal edge colorings of infinite lattice graphs. In case a nearly minimal edge coloring is requested, the running time is O(μ2D4), where μ is the number of edges in one cell (or `basis graph') of the lattice graph and D is the maximum distance between two cells so that there is an edge from within one cell to the other. In case a minimal edge coloring is requested, we lack an upper bound on the running time, which we find need not pose a limitation in practice; we use the method to minimal edge color the meshes of all k-uniform tilings of the plane for k≤6, while utilizing modest computational resources. We find that all these lattice graphs are Vizing class~I. Relating edge colorings to quantum circuits, our work finds direct application by offering minimal-depth quantum circuits in the areas of quantum simulation, quantum optimization, and quantum state verification.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
KATTEMÖLLE, Joris, 2024. Edge coloring lattice graphsBibTex
@unpublished{Kattemolle2024color-71314, year={2024}, doi={10.48550/arXiv.2402.08752}, title={Edge coloring lattice graphs}, author={Kattemölle, Joris} }
RDF
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/71314"> <dc:contributor>Kattemölle, Joris</dc:contributor> <dc:creator>Kattemölle, Joris</dc:creator> <dc:language>eng</dc:language> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/71314"/> <dcterms:abstract>We develop the theory of the edge coloring of infinite lattice graphs, proving a necessary and sufficient condition for a proper edge coloring of a patch of a lattice graph to induce a proper edge coloring of the entire lattice graph by translation. This condition forms the cornerstone of a method that finds nearly minimal or minimal edge colorings of infinite lattice graphs. In case a nearly minimal edge coloring is requested, the running time is O(μ<sup>2</sup>D<sup>4</sup>), where μ is the number of edges in one cell (or `basis graph') of the lattice graph and D is the maximum distance between two cells so that there is an edge from within one cell to the other. In case a minimal edge coloring is requested, we lack an upper bound on the running time, which we find need not pose a limitation in practice; we use the method to minimal edge color the meshes of all k-uniform tilings of the plane for k≤6, while utilizing modest computational resources. We find that all these lattice graphs are Vizing class~I. Relating edge colorings to quantum circuits, our work finds direct application by offering minimal-depth quantum circuits in the areas of quantum simulation, quantum optimization, and quantum state verification.</dcterms:abstract> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dcterms:issued>2024</dcterms:issued> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2024-11-18T13:46:03Z</dc:date> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2024-11-18T13:46:03Z</dcterms:available> <dcterms:title>Edge coloring lattice graphs</dcterms:title> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/41"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/41"/> </rdf:Description> </rdf:RDF>