𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Elementary Bipartite Graphs and Unique Colourability

✍ Scribed by Gábor Bacsó

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
44 KB
Volume
23
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

The Clique-Pair-Conjecture (CPC) states that a uniquely colourable perfect graph, different from a clique, contains two maximum size cliques having a two element symmetric difference. One can make an auxiliary graph B from a minimal counterexample for the CPC (if any exists), this B is bipartite. We prove that B is elementary. Furthermore, we give a characterization of the minimal counterexamples, in terms of the constructed auxiliary graphs.

📜 SIMILAR VOLUMES

The chromatic uniqueness of complete bip
The chromatic uniqueness of complete bipartite graphs
✍ Shaoji Xu 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 585 KB

Xu, S., The chromatic uniqueness of complete bipartite graphs, Discrete Mathematics 94 (1991) 153-159. This paper is partitioned into two parts. In the first part we determine the maximum number of induced complete bipartite subgraphs in graphs with some given conditions. Using a theorem given in th

Total colouring regular bipartite graphs
Total colouring regular bipartite graphs is NP-hard
✍ Colin J.H. McDiarmid; Abdón Sánchez-Arroyo 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 437 KB

The total chromatic number of an arbitrary graph is the smallest number of colours needed to colour the edges and vertices of the graph so that no two adjacent or incident elements of the graph receive the same colour. In this paper we prove that the problem of determining the total chromatic number

Uniquely (m, k)τ-colourable graphs and k
Uniquely (m, k)τ-colourable graphs and k − τ-saturated graphs
✍ Gerhard Benadé; Izak Broere; Betsie Jonck; Marietjie Frick 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 518 KB

For a graph G, the path number r(G) is defined as the order of a longest path in G. An (m, k)~-colouring of a graph H is a partition of the vertex set of H into m subsets such that each subset induces a subgraph of H for which r is at most k. The k -z-chromatic number z~(H) is the least m for which