skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

Facial non-repetitive edge-coloring of plane graphs

Havet, Frédéric ; Jendrol', Stanislav ; Soták, Roman ; Škrabul'áková, Erika

Journal of graph theory, 2011-01, Vol.66 (1), p.38-48 [Periódico revisado por pares]

Hoboken: Wiley Subscription Services, Inc., A Wiley Company

Texto completo disponível

Citações Citado por
  • Título:
    Facial non-repetitive edge-coloring of plane graphs
  • Autor: Havet, Frédéric ; Jendrol', Stanislav ; Soták, Roman ; Škrabul'áková, Erika
  • Assuntos: Computer Science ; Discrete Mathematics ; edge coloring ; non-repetitive ; plane graph ; Thue sequences ; tree
  • É parte de: Journal of graph theory, 2011-01, Vol.66 (1), p.38-48
  • Notas: ark:/67375/WNG-LDGVW5L1-1
    istex:289EAF094886FB49E86DD0C1B985A5A42518F6CA
    European project FET-AEOLUS
    ArticleID:JGT20488
    Slovak Science and Technology Assistance Agency - No. APVV-0007-07
  • Descrição: A sequence r1, r2, …, r2n such that ri=rn+ i for all 1≤i≤n is called a repetition. A sequence S is called non‐repetitive if no block (i.e. subsequence of consecutive terms of S) is a repetition. Let G be a graph whose edges are colored. A trail is called non‐repetitive if the sequence of colors of its edges is non‐repetitive. If G is a plane graph, a facial non‐repetitive edge‐coloring of G is an edge‐coloring such that any facial trail (i.e. a trail of consecutive edges on the boundary walk of a face) is non‐repetitive. We denote π′f(G) the minimum number of colors of a facial non‐repetitive edge‐coloring of G. In this article, we show that π′f(G)≤8 for any plane graph G. We also get better upper bounds for π′f(G) in the cases when G is a tree, a plane triangulation, a simple 3‐connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound 4 for trees is tight. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 38–48, 2010
  • Editor: Hoboken: Wiley Subscription Services, Inc., A Wiley Company
  • Idioma: Inglês
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.