✦ LIBER ✦

Chromatic neighborhood sets

✍ Scribed by Molloy, Michael

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 242 KB
Volume: 31
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199908)31:4<303::aid-jgt5>3.0.co;2-g

No coin nor oath required. For personal study only.

✦ Synopsis

For each vertex v in a graph G, we denote by χ v the chromatic number of the subgraph induced by its neighborhood, and we set χ N (G) = {χ v : v ∈ V (G)}. We characterize those sets X for which there exists some G of prescribed size with X = χ N (G), and prove a related conjecture of Fajtlowicz. We also discuss those graphs that are extremal with respect to χ N (G).

📜 SIMILAR VOLUMES

Extremal problems for chromatic neighbor

Extremal problems for chromatic neighborhood sets

✍ André Kündgen; Michael Molloy 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 79 KB

## Abstract The chromatic neighborhood sequence of a graph G is the list of the chromatic numbers of the subgraphs induced by the neighborhoods of the vertices. We study the maximum multiplicity of this sequence, proving, amongst other things, that if a chromatic neighborhood sequence has __t__ dis

Independent sets and 2-factors in edge-c

Independent sets and 2-factors in edge-chromatic-critical graphs

✍ Stefan Grünewald; Eckhard Steffen 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 66 KB 👁 1 views

## Abstract In 1968, Vizing made the following two conjectures for graphs which are critical with respect to the chromatic index: (1) every critical graph has a 2‐factor, and (2) every independent vertex set in a critical graph contains at most half of the vertices. We prove both conjectures for cr

Circular Chromatic Numbers of Distance G

Circular Chromatic Numbers of Distance Graphs with Distance Sets Missing Multiples

✍ Lingling Huang; Gerard J Chang 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 114 KB

Given positive integers m, k, s with m > sk, let D m,k,s represent the set {1, 2, . . . , m}\{k, 2k, . . . , sk}. The distance graph G(Z , D m,k,s ) has as vertex set all integers Z and edges connecting i and j whenever |i -j| ∈ D m,k,s . This paper investigates chromatic numbers and circular chroma

Circular chromatic number of distance gr

Circular chromatic number of distance graphs with distance sets of cardinality 3

✍ Xuding Zhu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

## Abstract Suppose __D__ is a subset of __R__^+^. The distance graph __G__(__R, D__) is the graph with vertex set __R__ in which two vertices __x__,__y__ are adjacent if |__x__−__y__| ∈ __D__. This study investigates the circular chromatic number and the fractional chromatic number of distance gra

A Correlation Inequality Involving Stabl

A Correlation Inequality Involving Stable Set and Chromatic Polynomials

✍ G.E. Farr 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 230 KB

Suppose each vertex of a graph \(G\) is chosen with probability \(p\), these choices being independent. Let \(A(G, p)\) be the probability that no two chosen vertices are adjacent. This is essentially the clique polynomial of the complement of \(G\) which has been extensively studied in a variety of

Your Neighborhood Legend: Neighborhood #10

✍ Tarrah Anders 📂 Fiction 🏛 Tarrah Anders, LLC 🌐 English ⚖ 58 KB 👁 3 views

Every town has someone who left and made their lives something spectacular. Caleb Mercy left town at the first chance he got and did just that. Leaving behind his father and his high school sweetheart without a word. He’s brought back to the small town of Mercy to be by his father’s side in his