Full metadata record
DC poleHodnotaJazyk
dc.contributor.authorKarabáš, Ján
dc.contributor.authorMáčajová, Edita
dc.contributor.authorNedela, Roman
dc.contributor.authorŠkoviera, Martin
dc.date.accessioned2022-09-12T10:00:24Z-
dc.date.available2022-09-12T10:00:24Z-
dc.date.issued2022
dc.identifier.citationKARABÁŠ, J. MÁČAJOVÁ, E. NEDELA, R. ŠKOVIERA, M. Girth, oddness, and colouring defect of snarks. DISCRETE MATHEMATICS, 2022, roč. 345, č. 11, s. nestránkováno. ISSN: 0012-365Xcs
dc.identifier.issn0012-365X
dc.identifier.uri2-s2.0-85132327227
dc.identifier.urihttp://hdl.handle.net/11025/49639
dc.description.abstractBarevný defekt kubického grafu je mnimální počet hran nepokrytý třema perfektními párováními. Kubický graf má defekt 0 právě tehdy, když je hranově 3-obarvitelný. Naším cílem je studovat souvislost obvodu a lichosti kubického grafu a barevného defektu. Skonstruujeme nekonečně mnoho 5-cyklicky souvislých kubických grafů lichosti 2 libovolně velkého obvodu a libovolne velkého barevného defektucs
dc.format10 s.cs
dc.format.mimetypeapplication/pdf
dc.language.isoenen
dc.publisherElsevieren
dc.relation.ispartofseriesDiscrete Mathematicsen
dc.rightsPlný text je přístupný v rámci univerzity přihlášeným uživatelům.cs
dc.rights© Elsevieren
dc.subjectsnark, lichost, obvod, barevný defektcs
dc.titleGirth, oddness, and colouring defect of snarksen
dc.title.alternativeObvod, lichost, a barevný defekt snarkůcs
dc.typečlánekcs
dc.typearticleen
dc.rights.accessrestrictedAccessen
dc.type.versionpublishedVersionen
dc.description.abstract-translatedThe colouring defect of a cubic graph, introduced by Steffen in 2015, is the minimum number of edges that are left uncovered by any set of three perfect matchings. Since a cubic graph has defect 0 if and only if it is 3-edge-colourable, this invariant can measure how much a cubic graph differs from a 3-edge-colourable graph. Our aim is to examine the relationship of colouring defect to oddness, an extensively studied measure of uncolourability of cubic graphs, defined as the smallest number of odd circuits in a 2factor. We show that there exist cyclically 5-edge-connected snarks (cubic graphs with no 3-edge-colouring) of oddness 2 and arbitrarily large colouring defect. This result is achieved by means of a construction of cyclically 5-edge-connected snarks with oddness 2 and arbitrarily large girth. The fact that our graphs are cyclically 5-edge-connected significantly strengthens a similar result of Jin and Steffen (2017), which only guarantees graphs with cyclic connectivity at most 3. At the same time, our result improves Kochol's original construction of snarks with large girth (1996) in that it provides infinitely many nontrivial snarks of any prescribed girth g >= 5, not just girth at least g.en
dc.subject.translatedsnark, oddness, girth, colouring defecten
dc.identifier.doi10.1016/j.disc.2022.113040
dc.type.statusPeer-revieweden
dc.identifier.document-number818515100013
dc.identifier.obd43936518
Vyskytuje se v kolekcích:Články / Articles (NTIS)
OBD

Soubory připojené k záznamu:
Soubor VelikostFormát 
girthsnarks.pdf401,18 kBAdobe PDFZobrazit/otevřít  Vyžádat kopii
Zobrazit minimální záznam Zobrazit statistiky


Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam: http://hdl.handle.net/11025/49639

Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.

hledání
navigace
  1. DSpace at University of West Bohemia
  2. Publikační činnost / Publications
  3. OBD