Baranyai's partition characterisation of (3,6)-tight graphs
Statement
Let be a graph with at least vertices. A graph is -tight when and every vertex subset with at least two vertices spans at most edges. For an edge , write for the graph obtained by contracting . A graph is -tight when and every vertex subset with at least two vertices spans at most edges.
The partition characterisation conjecture. The graph is -tight if and only if, for every edge , there exists a partition of such that
, and each of the graphs
is -tight.
This conjecture is proposed as a correction to a claimed combinatorial characterisation of minimal -rigidity. The paper presents a counterexample to the earlier characterisation and suggests that the stated partition condition may provide the appropriate characterisation; its resolution is not established here.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.