ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a graph with k≥1k\ge 1 pendant vertices and chromatic number χ(G)\chi(G) satisfying k≥χ(G)−1k\ge \chi(G)-1. The graphs K(2;a,b)K(2;a,b), caterpillar graphs in the cited theorem, Ct(3;n1,0,n3)Ct(3;n_1,0,n_3), and the indicated corona graphs Pm⊙OnP_m\odot O_n, Cm⊙OnC_m\odot O_n, and Km⊙OnK_m\odot O_n are defined by the displayed exceptional conditions. Exceptional-graph conjecture. All graphs GG with k≥χ(G)−1k\ge\chi(G)-1 pendants have χla(G)=k+1\chi_{la}(G)=k+1, except the following cases: χla(K(2;a,b))=a+b+2\chi_{la}(K(2;a,b))=a+b+2 for a≥b≥2a\ge b\ge2 and a<b(b+1)/2a<b(b+1)/2; the caterpillar graphs in Theorem~; χla(Ct(3;n1,0,n3))=n1+n3+2\chi_{la}(Ct(3;n_1,0,n_3))=n_1+n_3+2 under the stated inequalities and congruence condition; and the three stated corona families with their displayed values or lower bound. This is presented as a proposed global classification; no resolution is supplied in the paper.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.