Publikation:

Edge coloring lattice graphs

Lade...
Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2024

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Preprint
Publikationsstatus
Published

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)
530 Physik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690KATTEMÖLLE, Joris, 2024. Edge coloring lattice graphs
BibTex
@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(μ&lt;sup&gt;2&lt;/sup&gt;D&lt;sup&gt;4&lt;/sup&gt;), 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>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen