umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On restricted colorings of (d,s)-edge colorable graphs
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
(English)Manuscript (preprint) (Other academic)
Abstract [en]

A cycle is 2-colored if its edges are properly colored by two distinct colors. A (d,s)-edge colorable graph G is a d-regular graph that admits a proper d-edge coloring in which every edge of G is in at least s−1 2-colored 4-cycles. Given a (d,s)-edge colorable graph G and a list assigment L of forbidden colors for the edges of G satisfying certain sparsity conditions, we prove that there is a proper d-edge coloring of Gthat avoids L, that is, a proper edge coloring φ of G such that φ(e)∉L(e) for every edge e of G.

Keywords [en]
list assigment, restricted colorings
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-158320OAI: oai:DiVA.org:umu-158320DiVA, id: diva2:1306362
Available from: 2019-04-23 Created: 2019-04-23 Last updated: 2019-04-29
In thesis
1. On avoiding and completing colorings
Open this publication in new window or tab >>On avoiding and completing colorings
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

All of my papers are related to the problem of avoiding and completing an edge precoloring of a graph. In more detail, given a graph G and a partial proper edge precoloring φ of G and a list assignment L for every non-colored edge of G, can we extend φ to a proper edge coloring of G which avoids L? 

In Paper I, G is the d-dimensional hypercube graph Qd, a partial proper edge precoloring φ and a list assignment L must satisfy certain sparsity conditions. Paper II still deals with the hypercube graph Qd, but the list assignment L for every edge of Qd is an empty set and φ must be a partial proper edge precoloring of at most d-1 edges. In Paper III, G is a (d,s)-edge colorable graph; that is G has a proper d-edge coloring, where every edge is contained in at least s-1 2-colored 4-cycles, L must satisfy certain sparsity conditions and we do not have a partial proper edge precoloring φ on edges of G. The problem in Paper III is also considered in Paper IV and Paper V, but here G can be seen as the complete 3-uniform 3-partite hypergraph K3n,n,n, where n is a power of two in paper IV and n is an even number in paper V.

Place, publisher, year, edition, pages
Umeå: Umeå University, 2019. p. 11
Series
Research report in mathematics, ISSN 1653-0810 ; 66/19
Keywords
Graph coloring, precoloring, list assignment
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-158343 (URN)978-91-7855-055-5 (ISBN)
Public defence
2019-05-24, MA121, MIT-huset, Umeå, 10:15 (English)
Opponent
Supervisors
Available from: 2019-05-03 Created: 2019-04-24 Last updated: 2019-04-29Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

URL

Authority records BETA

Pham, Lan Anh

Search in DiVA

By author/editor
Pham, Lan Anh
By organisation
Department of Mathematics and Mathematical Statistics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 49 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf