Acyclic k-strong coloring of maps on surfaces

O. V. Borodin; A. V. Kostochka; A. Raspaud; E. Sopena

doi:10.1007/BF02675788

Acyclic k-strong coloring of maps on surfaces

O. V. Borodin, A. V. Kostochka, A. Raspaud, E. Sopena

Research output: Contribution to journal › Article › peer-review

Abstract

A coloring of graph vertices is called acyclic if the ends of each edge are colored in distinct colors and there are no two-colored cycles. Suppose each face of rank not greater than k, k ≥ 4, on a surface S^N is replaced by the clique on the same set of vertices. Then the pseudograph obtained in this way can be colored acyclically in a set of colors whose cardinality depends linearly on N and on k. Results of this kind were known before only for 1 ≤ N ≤ 2 and 3 ≤ k ≤ 4.

Original language	English (US)
Pages (from-to)	29-35
Number of pages	7
Journal	Mathematical Notes
Volume	67
Issue number	1
DOIs	https://doi.org/10.1007/BF02675788
State	Published - 2000
Externally published	Yes

Keywords

Acyclic coloring
Acyclic graphs
Cliques
Embedded graphs
Map coloring

ASJC Scopus subject areas

Mathematics(all)

Online availability

10.1007/BF02675788

Library availability

Discover UIUC Full Text

Cite this

@article{8a2e85b7a2a84bfdabc9132ee210cb7b,

title = "Acyclic k-strong coloring of maps on surfaces",

abstract = "A coloring of graph vertices is called acyclic if the ends of each edge are colored in distinct colors and there are no two-colored cycles. Suppose each face of rank not greater than k, k ≥ 4, on a surface SN is replaced by the clique on the same set of vertices. Then the pseudograph obtained in this way can be colored acyclically in a set of colors whose cardinality depends linearly on N and on k. Results of this kind were known before only for 1 ≤ N ≤ 2 and 3 ≤ k ≤ 4.",

keywords = "Acyclic coloring, Acyclic graphs, Cliques, Embedded graphs, Map coloring",

author = "Borodin, {O. V.} and Kostochka, {A. V.} and A. Raspaud and E. Sopena",

year = "2000",

doi = "10.1007/BF02675788",

language = "English (US)",

volume = "67",

pages = "29--35",

journal = "Mathematical Notes of the Academy of Sciences of the USSR",

issn = "1757-7489",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Acyclic k-strong coloring of maps on surfaces

AU - Borodin, O. V.

AU - Kostochka, A. V.

AU - Raspaud, A.

AU - Sopena, E.

PY - 2000

Y1 - 2000

N2 - A coloring of graph vertices is called acyclic if the ends of each edge are colored in distinct colors and there are no two-colored cycles. Suppose each face of rank not greater than k, k ≥ 4, on a surface SN is replaced by the clique on the same set of vertices. Then the pseudograph obtained in this way can be colored acyclically in a set of colors whose cardinality depends linearly on N and on k. Results of this kind were known before only for 1 ≤ N ≤ 2 and 3 ≤ k ≤ 4.

AB - A coloring of graph vertices is called acyclic if the ends of each edge are colored in distinct colors and there are no two-colored cycles. Suppose each face of rank not greater than k, k ≥ 4, on a surface SN is replaced by the clique on the same set of vertices. Then the pseudograph obtained in this way can be colored acyclically in a set of colors whose cardinality depends linearly on N and on k. Results of this kind were known before only for 1 ≤ N ≤ 2 and 3 ≤ k ≤ 4.

KW - Acyclic coloring

KW - Acyclic graphs

KW - Cliques

KW - Embedded graphs

KW - Map coloring

UR - http://www.scopus.com/inward/record.url?scp=7544236914&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=7544236914&partnerID=8YFLogxK

U2 - 10.1007/BF02675788

DO - 10.1007/BF02675788

M3 - Article

AN - SCOPUS:7544236914

SN - 1757-7489

VL - 67

SP - 29

EP - 35

JO - Mathematical Notes of the Academy of Sciences of the USSR

JF - Mathematical Notes of the Academy of Sciences of the USSR

IS - 1

ER -

Acyclic k-strong coloring of maps on surfaces

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this