Estimating the minimal number of colors in acyclic k-strong colorings of maps on surfaces

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

doi:10.1023/A:1019808819476

Estimating the minimal number of colors in acyclic k-strong colorings 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 the vertices of a graph 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 k, k ≥ 4, in a map on a surface S ^N is replaced by the clique having the same number of vertices. It is proved in [1] that the resulting pseudograph admits an acyclic coloring with the number of colors depending linearly on N and k. In the present paper we prove a sharper estimate 55(-Nk) ^4/7 for the number of colors provided that k ≥ 1 and N ≥ 5 ⁷k ^4/3.

Original language	English (US)
Pages (from-to)	31-33
Number of pages	3
Journal	Mathematical Notes
Volume	72
Issue number	1-2
DOIs	https://doi.org/10.1023/A:1019808819476
State	Published - 2002
Externally published	Yes

Keywords

Acyclic colorings
Graphs on surfaces
K-strong colorings

ASJC Scopus subject areas

General Mathematics

Online availability

10.1023/A:1019808819476

Library availability

Discover UIUC Full Text

Cite this

@article{77f682e0c71e4441bd6183402215ffd8,

title = "Estimating the minimal number of colors in acyclic k-strong colorings of maps on surfaces",

abstract = "A coloring of the vertices of a graph 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 k, k ≥ 4, in a map on a surface S N is replaced by the clique having the same number of vertices. It is proved in [1] that the resulting pseudograph admits an acyclic coloring with the number of colors depending linearly on N and k. In the present paper we prove a sharper estimate 55(-Nk) 4/7 for the number of colors provided that k ≥ 1 and N ≥ 5 7k 4/3.",

keywords = "Acyclic colorings, Graphs on surfaces, K-strong colorings",

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

note = "The research of the first author was supported in part by the Russian Foundation for Basic Research under grant no. 97-01-01075 and by INTAS under grant no. 97-1001. The research of the second author was supported in part by the Russian Foundation for Basic Research under grant no. 99-01-00581, and by the NWO-grant no. 047-008-006. The research of the third and the fourth author was supported in part by the Joint scientific NATO grant no. 97-1519.",

year = "2002",

doi = "10.1023/A:1019808819476",

language = "English (US)",

volume = "72",

pages = "31--33",

journal = "Mathematical Notes",

issn = "0001-4346",

publisher = "Springer",

number = "1-2",

}

TY - JOUR

T1 - Estimating the minimal number of colors in acyclic k-strong colorings of maps on surfaces

AU - Borodin, O. V.

AU - Kostochka, A. V.

AU - Raspaud, A.

AU - Sopena, E.

N1 - The research of the first author was supported in part by the Russian Foundation for Basic Research under grant no. 97-01-01075 and by INTAS under grant no. 97-1001. The research of the second author was supported in part by the Russian Foundation for Basic Research under grant no. 99-01-00581, and by the NWO-grant no. 047-008-006. The research of the third and the fourth author was supported in part by the Joint scientific NATO grant no. 97-1519.

PY - 2002

Y1 - 2002

N2 - A coloring of the vertices of a graph 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 k, k ≥ 4, in a map on a surface S N is replaced by the clique having the same number of vertices. It is proved in [1] that the resulting pseudograph admits an acyclic coloring with the number of colors depending linearly on N and k. In the present paper we prove a sharper estimate 55(-Nk) 4/7 for the number of colors provided that k ≥ 1 and N ≥ 5 7k 4/3.

AB - A coloring of the vertices of a graph 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 k, k ≥ 4, in a map on a surface S N is replaced by the clique having the same number of vertices. It is proved in [1] that the resulting pseudograph admits an acyclic coloring with the number of colors depending linearly on N and k. In the present paper we prove a sharper estimate 55(-Nk) 4/7 for the number of colors provided that k ≥ 1 and N ≥ 5 7k 4/3.

KW - Acyclic colorings

KW - Graphs on surfaces

KW - K-strong colorings

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

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

U2 - 10.1023/A:1019808819476

DO - 10.1023/A:1019808819476

M3 - Article

AN - SCOPUS:0141848613

SN - 0001-4346

VL - 72

SP - 31

EP - 33

JO - Mathematical Notes

JF - Mathematical Notes

IS - 1-2

ER -

Estimating the minimal number of colors in acyclic k-strong colorings of maps on surfaces

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this