| 1. |
- Casselgren, Carl Johan, et al.
(författare)
-
Restricted extension of sparse partial edge colorings of hypercubes
- 2020
-
Ingår i: Discrete Mathematics. - : ELSEVIER. - 0012-365X .- 1872-681X. ; 343:11
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the following type of question: Given a partial proper d-edge coloring of the d-dimensional hypercube Qd, and lists of allowed colors for the non-colored edges of Qd, can we extend the partial coloring to a proper d-edge coloring using only colors from the lists? We prove that this question has a positive answer in the case when both the partial coloring and the color lists satisfy certain sparsity conditions. (C) 2020 Elsevier B.V. All rights reserved.
|
|
| 2. |
- Häggkvist, Roland, et al.
(författare)
-
Cycle double covers and spanning minors II
- 2006
-
Ingår i: Discrete Mathematics. - Amsterdam : North-Holland. - 0012-365X .- 1872-681X. ; 306:8-9, s. 762-778
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we continue our investigations from [R. Häggkvist, K. Markström, Cycle double covers and spanning minors, Technical Report 07, Department of Mathematics, Umeå University, Sweden, 2001, J. Combin. Theory, Ser. B, to appear] regarding spanning subgraphs which imply the existence of cycle double covers. We prove that if a cubic graph G has a spanning subgraph isomorphic to a subdivision of a bridgeless cubic graph on at most 10 vertices then G has a CDC. A notable result is thus that a cubic graph with a spanning Petersen minor has a CDC, a result also obtained by Goddyn [L. Goddyn, Cycle covers of graphs, Ph.D. Thesis, University of Waterloo, 1988].
|
|
| 3. |
- Hägglund, Jonas, 1982-, et al.
(författare)
-
On stable cycles and cycle double covers of graphs with large circumference
- 2012
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 312:17, s. 2540-2544
-
Tidskriftsartikel (refereegranskat)abstract
- A cycle C in a graph is called stable if there exists no other cycle D in the same graph such that V(C)⊆V(D). In this paper, we study stable cycles in snarks and we show that if a cubic graph G has a cycle of length at least |V(G)|−9 then it has a cycle double cover. We also give a construction for an infinite snark family with stable cycles of constant length and answer a question by Kochol by giving examples of cyclically 5-edge connected snarks with stable cycles.
|
|
| 4. |
- Markström, Klas
(författare)
-
Even cycle decompositions of 4-regular graphs and line graphs
- 2012
-
Ingår i: Discrete Mathematics. - Amsterdam : Elsevier BV. - 0012-365X .- 1872-681X. ; 312:17, s. 2676-2681
-
Tidskriftsartikel (refereegranskat)abstract
- An even cycle decomposition of a graph is a partition of its edge into even cycles. We first give some results on the existence of even cycle decomposition in general 4-regular graphs, showing that K 5 is not the only graph in this class without such a decomposition. Motivated by connections to the cycle double cover conjecture we go on to consider even cycle decompositions of line graphs of 2-connected cubic graphs. We conjecture that in this class even cycle decompositions always exists and prove the conjecture for cubic graphs with oddness at most 2. We also discuss even cycle double covers of cubic graphs.
|
|
| 5. |
- Markström, Klas
(författare)
-
Extremal hypergraphs and bounds for the Turan density of the 4-uniform K-5
- 2009
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 309:16, s. 5231-5234
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we find, for n <= 16, the maximum number of edges in a 4-uniform hypergraph which does not have the complete 4-uniform hypergraph on five vertices, K-5(4), as a subgraph. Equivalently, we find all optimal (n, n-4, n-5) covering designs for n <= 16. Using these results we find a new upper bound for the Turin density of K-5(4). pi(K-5(4)) <= 1753/2380 = 0.73655.... Finally we make some notes on the structure of the extremal 4-graphs for this problem and the conjectured extremal family. (C) 2009 Published by Elsevier B.V.
|
|
