The Erdős--Faber--Lov\'{a}sz Conjecture revisited

The Erdős--Faber--Lov\'{a}sz Conjecture, posed in 1972, states that if a graph \(G\) is the union of \(n\) cliques of order \(n\) (referred to as defining \(n\)-cliques) such that two cliques can share at most one vertex, then the vertices of \(G\) can be properly coloured using \(n\) colours....

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-12
Main Authors: Gauci, John Baptist, Zerafa, Jean Paul
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Graph coloring
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Erdős--Faber--Lov\'{a}sz Conjecture, posed in 1972, states that if a graph \(G\) is the union of \(n\) cliques of order \(n\) (referred to as defining \(n\)-cliques) such that two cliques can share at most one vertex, then the vertices of \(G\) can be properly coloured using \(n\) colours. Although still open after almost 50 years, it can be easily shown that the conjecture is true when every shared vertex belongs to exactly two defining \(n\)-cliques. We here provide a quick and easy algorithm to colour the vertices of \(G\) in this case, and discuss connections with clique-decompositions and edge-colourings of graphs.
ISSN:2331-8422
DOI:10.48550/arxiv.2103.00875