𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Subgraphs in vertex neighborhoods of Kr-free graphs

✍ Scribed by Jorgen Bang-Jensen; Stephan Brandt

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
111 KB
Volume
47
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In a K~r~‐free graph, the neighborhood of every vertex induces a K~rβ€‰βˆ’β€‰1~‐free subgraph. The K~r~‐free graphs with the converse property that every induced K~rβ€‰βˆ’β€‰1~‐free subgraph is contained in the neighborhood of a vertex are characterized, based on the characterization in the case rβ€‰βˆ’β€‰3 due to Pach [8]. Β© 2004 Wiley Periodicals, Inc. J Graph Theory 47: 29–38, 2004

πŸ“œ SIMILAR VOLUMES

Kr-Free Uniquely Vertex Colorable Graphs
Kr-Free Uniquely Vertex Colorable Graphs with Minimum Possible Edges
✍ S. Akbari; V.S. Mirrokni; B.S. Sadjad πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 112 KB

We construct counterexamples to the conjecture of Xu (1990, J. Combin. Theory Ser. B 50, 319 320) that every uniquely r-colorable graph of order n with exactly (r&1) n&( r2 ) edges must contain a K r . ## 2001 Academic Press Harary et al. [4] constructed uniquely r-colorable graphs containing no

Regular factors in vertex-deleted subgra
Regular factors in vertex-deleted subgraphs of regular graphs
✍ P. Katerinis πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 258 KB

Let G be a 2r-regular, 2r-edge-connected graph of odd order and m be an integer such that 1 2rw(W)+2ec(S',S')-2 c d,-&)+2rlS'I. ES' (12) But CxsS' ## dc-o(x)=&sS dG-D(x)+dc-&)=CXEs dG,-D(x)+e&,S)+dG-&). Thus (12) implies, ## 2rIDI>2ro(W)+2eG(S',S')-2 c dc,-o(x)+e,(u,S)+d,-,(u) +WS'I. XC.7