𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The chromaticity of complete bipartite graphs with at most one edge deleted

✍ Scribed by C. P. Teo; K. M. Koh

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
364 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let K(p, q), p ≤ q, denote the complete bipartite graph in which the two partite sets consist of p and q vertices, respectively. In this paper, we prove that (1) the graph K(p, q) is chromatically unique if p ≥ 2; and (2) the graph K(p, q) ‐ e obtained by deleting an edge e from K(p, q) is chromatically unique if p ≥ 3. The first result was conjectured by Salzberg, López, and Giudici, who also proved the second result under the condition that q ‐ p ≤ 1.

📜 SIMILAR VOLUMES

NP completeness of the edge precoloring
NP completeness of the edge precoloring extension problem on bipartite graphs
✍ Jiří Fiala 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 63 KB 👁 1 views

## Abstract We show that the following problem is __NP__ complete: Let __G__ be a cubic bipartite graph and __f__ be a precoloring of a subset of edges of __G__ using at most three colors. Can __f__ be extended to a proper edge 3‐coloring of the entire graph __G__? This result provides a natural co

On the density of 2-colorable 3-graphs i
On the density of 2-colorable 3-graphs in which any four points span at most two edges
✍ Klas Markström; John Talbot 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB 👁 1 views

## Abstract Let __ex__~2~(__n, K__) be the maximum number of edges in a 2‐colorable __K__‐free 3‐graph (where __K__={123, 124, 134} ). The 2‐chromatic Turán density of __K__ is \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}$\pi\_{2}({K}\_{4}^-) =lim\_{{n}\to \infty} {ex}\_{2}