On acyclic colorings of direct products

Špacapan, Simon; Tepeh, Aleksandra

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	On acyclic colorings of direct products
Authors:	ID Špacapan, Simon (Author) ID Tepeh, Aleksandra (Author)
Files:	Discussiones_Mathematicae_Graph_Theory_2008_Spacapan,_Tepeh_On_acyclic_colorings_of_direct_products.pdf (142,13 KB) MD5: D9B4EBB189ABF137C6F5A73BF3A66322 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1363
Language:	English
Work type:	Scientific work
Typology:	1.01 - Original Scientific Article
Organization:	FS - Faculty of Mechanical Engineering
Abstract:	A coloring of a graph $G$ is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees $T_1$ and $T_2$ equals $\min\{ \Delta(T_1) + 1, \Delta(T_2) + 1\}$ . We also prove that the acyclic chromatic number of direct product of two complete graphs $K_m$ and $K_n$ is $mn-m-2$ , where $m \ge n \ge 4$ . Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised.
Keywords:	mathematics, graph theory, coloring, acyclic coloring, distance-two coloring, direct product
Publication status:	Published
Publication version:	Version of Record
Year of publishing:	2008
Number of pages:	str. 323-333
Numbering:	Letn. 28, št. 2
PID:	20.500.12556/DKUM-65349
ISSN:	1234-3099
UDC:	519.17
ISSN on article:	1234-3099
COBISS.SI-ID:	14893401
NUK URN:	URN:SI:UM:DK:8LGTYPFJ
Publication date in DKUM:	31.03.2017
Views:	909
Downloads:	132
Metadata:
Categories:	Misc.
:	ŠPACAPAN, Simon and TEPEH, Aleksandra, 2008, On acyclic colorings of direct products. Discussiones mathematicae : Graph theory [online]. 2008. Vol. 28, no. 2, p. 323–333. [Accessed 1 April 2025]. Retrieved from: https://dk.um.si/IzpisGradiva.php?lang=eng&id=65349 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Similar works from other repositories:

No similar works found

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:	Discussiones mathematicae : Graph theory
Shortened title:	Discuss. Math., Graph Theory
Publisher:	Technical University Press
ISSN:	1234-3099
COBISS.SI-ID:	7487065

Document is financed by a project

Funder:	ARRS - Slovenian Research Agency
Project number:	P1-0297
Name:	Teorija grafov

Licences

License:	CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Link:	http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:	The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Licensing start date:	31.03.2017

Secondary language

Language:	Slovenian
Title:	Aciklična barvanja direktnih produktov
Abstract:	Barvanje grafa je aciklično, če je poljubna unija dveh barvnih razredov gozd. Dokazano je, da je aciklično kromatično število produkta dveh dreves $T_1$ in $T_2$ enako $\min\{ \Delta(T_1)+1, \Delta(T_2)+1\}$ . Prav tako je dokazano, da je aciklično kromatično število dveh polnih grafov $K_m$ in $K_n$ enako $mn-m-2$ , kjer je $m \ge n \ge 4$ . Številne meje za aciklično kromatično število so podane in v zvezi s tem so zastavljena nekatera vprašanja.
Keywords:	matematika, teorija grafov, barvanje, aciklično barvanje, barvanje s pogojem na razdalji dva, direktni produkt grafov

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back