Treewidth may have too many equivalent definitions, but there is another parameter in graph theory with too many names. It is the intersection number, the edge clique cover number, the clique edge cover number, the clique cover number, or the R-content. The computational problem of finding this number has been called the intersection number problem, the intersection graph basis problem, covering by cliques, the edge clique cover problem, the clique edge cover problem and the keyword conflict problem.
The problem can be expressed either as covering the edges of a graph with as few cliques as possible, or as representing the vertices of a graph by sets with as few total elements as possible so that adjacency corresponds to having a nonempty intersection. Its applications involve concisely representing conflicts between pairs of things, scheduling meetings so that all compatible pairs of participants meet and no incompatible participants meet, allocating bandwidth on fiber optic networks, generating compact letter displays that visualize the distinguishability of statistical variables, and analyzing biological food webs and protein interactions. Anyway, it is now a Good Article on Wikipedia: https://en.wikipedia.org/wiki/Intersection_number_(graph_theory)
0xDE
npub1r0…k9e4y
2025-11-19 22:24:08 UTC
Author Public Key
npub1r0rmlr8tq9rpk40ungugany0ywdnkeftk997zpvuwjjtdq4k6quqck9e4ySeen on
wss://relay.ditto.pubPublished at
2025-11-19 22:24:08 UTCEvent JSON
{
"id": "c96c630a238f4d8877fe897a29c7c267247c8f246befa0a87f9f61b97f1bdab0",
"pubkey": "1bc7bf8ceb01461b55fc9a388ecc8f239b3b652bb14be1059c74a4b682b6d038",
"created_at": 1763591048,
"kind": 1,
"tags": [
[
"proxy",
"https://mathstodon.xyz/users/11011110/statuses/115578702968747184",
"activitypub"
],
[
"client",
"Mostr",
"31990:6be38f8c63df7dbf84db7ec4a6e6fbbd8d19dca3b980efad18585c46f04b26f9:mostr",
"wss://relay.ditto.pub/"
]
],
"content": "Treewidth may have too many equivalent definitions, but there is another parameter in graph theory with too many names. It is the intersection number, the edge clique cover number, the clique edge cover number, the clique cover number, or the R-content. The computational problem of finding this number has been called the intersection number problem, the intersection graph basis problem, covering by cliques, the edge clique cover problem, the clique edge cover problem and the keyword conflict problem.\n\nThe problem can be expressed either as covering the edges of a graph with as few cliques as possible, or as representing the vertices of a graph by sets with as few total elements as possible so that adjacency corresponds to having a nonempty intersection. Its applications involve concisely representing conflicts between pairs of things, scheduling meetings so that all compatible pairs of participants meet and no incompatible participants meet, allocating bandwidth on fiber optic networks, generating compact letter displays that visualize the distinguishability of statistical variables, and analyzing biological food webs and protein interactions. Anyway, it is now a Good Article on Wikipedia: https://en.wikipedia.org/wiki/Intersection_number_(graph_theory)",
"sig": "d1f9fad6a3021c6a3b03d2586481de754d92d8ef92af09067d8c92ad8647c2b9edfbfc1aa88bf2c0c244fb167d5a0f5eea0bc26a508c703112f86d27669833d2"
}