✦ LIBER ✦

On generalized graph colorings

✍ Scribed by Jason I. Brown; Derek G. Corneil

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 610 KB
Volume: 11
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190110113

No coin nor oath required. For personal study only.

✦ Synopsis

Given a property P, graph G. and k 2 0, a P k-coloring is a function 7r: V(G) + { I , ... , k) such that the subgraph induced by each color class has property P; x ( G : P ) is the least k, for which G has a P k-coloring. We investigate here the theory of P colorings. Generalizations of the wellknown notions of vertex criticality and unique colorability are discussed, and w e extend a theorem of Erdos to Pchromatic graphs.

NOTATION AND BACKGROUND

In this paper, all graphs are finite, undirected, and without loops or multiple edges, and isomorphic graphs will be considered identical. The term subgraph will always stand for "induced subgraph" and we write H A G to denote H is a subgraph of G; for U V ( G ) , (U)c (or ( U ) if no ambiguity arises) denotes the subgraph of G induced by U . Unless otherwise stated, different graphs are assumed to be disjoint. The parameters a, w , y , and x denote, respectively, the independence number, the clique number, the girth, and the chromatic number. For other standard notation, we follow [ I ) .

Let G denote the set of all graphs. A subset P of G is a property iff KO, K , E

📜 SIMILAR VOLUMES

A Note on Graph Colorings and Graph Poly

A Note on Graph Colorings and Graph Polynomials

✍ Noga Alon; Michael Tarsi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 230 KB

## dedicated to professor w. t. tutte on the occasion of his eightieth birtday It is known that the chromatic number of a graph G=(V, E) with V= [1, 2, ..., n] exceeds k iff the graph polynomial f G => ij # E, i<j (x i &x j ) lies in certain ideals. We describe a short proof of this result, using

Extending Graph Colorings

✍ Michael O Albertson; Emily H Moore 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 172 KB

Suppose /(G)=r and P V(G). It is known that if the distance between any two vertices in P is at least 4, then any (r+1)-coloring of P extends to an (r+1)-coloring of all of G, but an r-coloring of P might not extend to an r-coloring of G. We show that if the distance between any two vertices in P is

A generalization of edge-coloring in gra

A generalization of edge-coloring in graphs

✍ S. Louis Hakimi; Oded Kariv 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 754 KB

Bounds are given on the number of colors required to color the edges of a graph (multigraph) such that each color appears at each vertex u at most m(u) times. The known results and proofs generalize in natural ways. Certain new edge-coloring problems, which have no counterparts when m(u) = 1 for all

Generalized graph entropies

✍ Matthias Dehmer; Abbe Mowshowitz 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB

Path homomorphisms, graph colorings, and

Path homomorphisms, graph colorings, and boolean matrices

✍ Jaroslav Nešetřil; Claude Tardif 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB

## Abstract We investigate bounds on the chromatic number of a graph __G__ derived from the nonexistence of homomorphisms from some path \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray\*}\vec{P}\end{eqnarray\*}\end{document} into some orientation \documentclass{

Planar graph colorings without short mon

Planar graph colorings without short monochromatic cycles

✍ Tomáš Kaiser; Riste Škrekovski 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

## Abstract It is well known that every planar graph __G__ is 2‐colorable in such a way that no 3‐cycle of __G__ is monochromatic. In this paper, we prove that __G__ has a 2‐coloring such that no cycle of length 3 or 4 is monochromatic. The complete graph __K__~5~ does not admit such a coloring. On