Some results on the structure of multipoles in the study of snarks (Q2260618): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / arXiv ID
 
Property / arXiv ID: 1308.0480 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Decomposition of snarks / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3937450 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4873828 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A simple and fast heuristic algorithm for edge-coloring of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4208548 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Construction of class two graphs with maximum vertex degree three / rank
 
Normal rank
Property / cites work
 
Property / cites work: Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable / rank
 
Normal rank
Property / cites work
 
Property / cites work: 6-decomposition of snarks / rank
 
Normal rank
Property / cites work
 
Property / cites work: Snarks without small cycles / rank
 
Normal rank
Property / cites work
 
Property / cites work: Decompositions and reductions of snarks / rank
 
Normal rank
Property / cites work
 
Property / cites work: Classification and characterizations of snarks / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3218161 / rank
 
Normal rank

Latest revision as of 20:21, 9 July 2024

scientific article
Language Label Description Also known as
English
Some results on the structure of multipoles in the study of snarks
scientific article

    Statements

    Some results on the structure of multipoles in the study of snarks (English)
    0 references
    0 references
    11 March 2015
    0 references
    Summary: Multipoles are the pieces we obtain by cutting some edges of a cubic graph in one or more points. As a result of the cut, a multipole \(M\) has vertices attached to a dangling edge with one free end, and isolated edges with two free ends. We refer to such free ends as semiedges, and to isolated edges as free edges. Every 3-edge-coloring of a multipole induces a coloring or state of its semiedges, which satisfies the parity lemma. Multipoles have been extensively used in the study of snarks, that is, cubic graphs which are not 3-edge-colorable. Some results on the states and structure of the so-called color complete and color closed multipoles are presented. In particular, we give lower and upper linear bounds on the minimum order of a color complete multipole, and compute its exact number of states. Given two multipoles \(M_1\) and \(M_2\) with the same number of semiedges, we say that \(M_1\) is reducible to \(M_2\) if the state set of \(M_2\) is a non-empty subset of the state set of \(M_1\) and \(M_2\) has less vertices than \(M_1\). The function \(v(m)\) is defined as the maximum number of vertices of an irreducible multipole with \(m\) semiedges. The exact values of ~\(v(m)\) are only known for \(m\leq 5\). We prove that tree and cycle multipoles are irreducible and, as a byproduct, that \(v(m)\) has a linear lower bound.
    0 references
    0 references
    0 references
    0 references
    0 references
    cubic graph
    0 references
    edge-coloring
    0 references
    snark
    0 references
    multipole
    0 references
    parity lemma
    0 references
    states
    0 references
    color complete
    0 references
    color closed
    0 references
    separable
    0 references
    irreducible
    0 references
    cycle
    0 references
    linear recurrence
    0 references
    0 references