The Chromatic Number of the Two-Packing of a Forest

Hong Wang () and Norbert Sauer ()
Additional contact information
Hong Wang: The University of Calgary, Department of Mathematics and Statistics
Norbert Sauer: The University of Calgary, Department of Mathematics and Statistics

A chapter in The Mathematics of Paul Erdős II, 2013, pp 143-166 from Springer

Abstract: Summary A two-packing of a graph G is a bijection σ : V (G)↦V (G) such that for every two adjacent vertices a, b ∈ V (G) the vertices σ(a) and σ(b) are not adjacent. It is known [2, 6] that every forest G which is not a star has a two-packing σ. If F σ is the graph whose vertices are the vertices of G and in which two vertices a, b are adjacent if and only if a, b or σ − 1(a), σ − 1(b) are adjacent in G then it is easy to see that the chromatic number of F σ is either 1, 2, 3 or 4. We characterize, for each number n between one and four all forests F which have a two-packing σ such that F σ has chromatic number n.

Keywords: Packing; Placement; Factorization; Tree; Forest; Chromatic number (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-7254-4_12

Ordering information: This item can be ordered from
http://www.springer.com/9781461472544

DOI: 10.1007/978-1-4614-7254-4_12

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().