Elementary graphs always have equal colour and choice numbers
Elementary graphs are chromatic-choosable
Discrete Mathematics
Summary
This paper deals with a special kind of network called an elementary graph where edges can be coloured in two specific colours under certain rules. The authors confirm a long-standing idea that, for these elementary graphs, the minimum number of colours needed normally matches the minimum number needed when each edge has a list of possible colours. This matches their largest fully connected component size. They use a combination of previous descriptions, mathematical theorems, and careful logical steps to prove their claim.
What this means in practice
- •For graph algorithm developers: Design graph colouring algorithms that guarantee list colouring matches chromatic number for elementary graphs, simplifying colouring constraints in network problems.
- •For communication network designers: Ensure frequency or channel assignments in networks modeled by elementary graphs can be optimally assigned even with restricted channel availability.
A theory result. No direct application yet.
Authors
Narayanan N, Nandana K. Vasudevan, K. Somasundaram
Abstract
A graph is \emph{elementary} if its edges can be coloured with two colours so that the two edges of every induced path on three vertices receive different colours. Elementary graphs are one of the two basic classes in the Chvátal--Sbihi decomposition of claw-free perfect graphs; they include all line graphs of bipartite multigraphs and all complements of bipartite graphs. We prove that every elementary graph $G$ satisfies $\ch(G)=χ(G)=ω(G)$, confirming for this class the conjecture of Gravier and Maffray that claw-free graphs are chromatic-choosable. The proof combines the Maffray--Reed description of elementary graphs as augmentations of line graphs of bipartite multigraphs, Galvin's theorem, an extremal (edge-maximal) choice of counterexample, and a Hall-type lemma describing how list colourings of a complete graph minus a matching can fail.