Complete graphs without proper subgraphs

DOI10.1016/J.DAM.2026.07.003MaRDI QIDQ7353724zbMATH OpenFDO

Authors Mengya He, Jinxia Liang, Colton Magnant, Chenxu Yang

Publication date 18 September 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2026.07.003

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

For a positive integer \(k\) and graphs \(G\), \(H\), the proper Ramsey number \(\operatorname{pr}_k(G:H)\) is the minimum \(N\) such that every \(k\)-edge-coloring of \(K_N\) contains either a properly colored copy of \(G\) or a monochromatic copy of \(H\). The authors first give structural characterizations of edge-colored complete graphs containing no proper \(K_3^+\), \(P_4\), or \(P_5\). For \(K_3^+\), they show that such graphs admit a partition arising from a blow-up of a \(P_3\)-colored \(K_4\), and give a more detailed four-condition description. For \(P_4\), either one color is used, or two colors are used with a vertex \(v\) such that \(K_n-v\) is a monochromatic clique and all edges from \(v\) to \(K_n-v\) have the other color. For \(P_5\), a four-part classification is obtained. Using these structures, they determine several proper Ramsey numbers, including \(\operatorname{pr}_k(P_4:G)\) and \(\operatorname{pr}_k(P_5:G)\) for small \(k\), and prove \(\operatorname{pr}_k(K_3^+:K_3)=\operatorname{gr}_k(K_3:K_3)\). Finally, via the Lovász Local Lemma, they derive a general lower bound for \(\operatorname{pr}_k(G:H)\) when \(H\) is a sufficiently large complete graph.

Cites work

This page was built for publication: Complete graphs without proper subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7353724)