✦ LIBER ✦

Achromatic number of fragmentable graphs

✍ Scribed by Keith Edwards

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 175 KB
Volume: 65
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20468

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A complete coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at least one edge. The achromatic number ψ(G) is the greatest number of colors in such a coloring. We say a class of graphs is fragmentable if for any positive ε, there is a constant C such that any graph in the class can be broken into pieces of size at most C by removing a proportion at most ε of the vertices. Examples include planar graphs and grids of fixed dimension. Determining the achromatic number of a graph is NP‐complete in general, even for trees, and the achromatic number is known precisely for only very restricted classes of graphs. We extend these classes very considerably, by giving, for graphs in any class which is fragmentable, triangle‐free, and of bounded degree, a necessary and sufficient condition for a sufficiently large graph to have a complete coloring with a given number of colors. For the same classes, this gives a tight lower bound for the achromatic number of sufficiently large graphs, and shows that the achromatic number can be determined in polynomial time. As examples, we give exact values of the achromatic number for several graph families. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:94–114, 2010

📜 SIMILAR VOLUMES

On the Achromatic Number of Hypercubes

✍ Yuval Roichman 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 96 KB

The achromatic number of a finite graph G, (G), is the maximum number of independent sets into which the vertex set may be partitioned, so that between any two parts there is at least one edge. For an m-dimensional hypercube P m 2 we prove that there exist constants 0<c 1 <c 2 , independent of m, su

Fragmentability of Graphs

✍ Keith Edwards; Graham Farr 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 128 KB

We define a parameter which measures the proportion of vertices which must be removed from any graph in a class in order to break the graph up into small (i.e. bounded sized) components. We call this the coefficient of fragmentability of the class. We establish values or bounds for the coefficient f

Overlap number of graphs

✍ Daniel W. Cranston; Nitish Korula; Timothy D. LeSaulnier; Kevin G. Milans; Chris 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB

## Abstract An __overlap representation__ of a graph __G__ assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The __overlap number__ φ(__G__) (introduced by Rosgen) is the minimum size of the union of the sets in su

Numbers of cubic graphs

✍ R. W. Robinson; N. C. Wormald 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 223 KB

## Abstract The numbers of unlabeled cubic graphs on __p = 2n__ points have been found by two different counting methods, the best of which has given values for __p ≦__ 40.

Crossing numbers of imbalanced graphs

✍ János Pach; József Solymosi; Gábor Tardos 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB

## Abstract The __crossing number__, cr(__G__), of a graph __G__ is the least number of crossing points in any drawing of __G__ in the plane. According to the Crossing Lemma of M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi, Theory and Practice of Combinatorics, North‐Holland, Amsterdam, New York,

Path chromatic numbers of graphs

✍ Jin Akiyama; Hiroshi Era; Severino V. Gervacio; Mamoru Watanabe 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB