Remarks on an Edge-coloring Problem | Zendy

Carlos Hoppen | Zendy; Hanno Lefmann | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Remarks on an Edge-coloring Problem

Author(s) -

Carlos Hoppen,

Hanno Lefmann

Publication year - 2019

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2019.08.045

Subject(s) - combinatorics , mathematics , rothschild , bipartite graph , edge coloring , vertex (graph theory) , complete bipartite graph , graph , fractional coloring , discrete mathematics , complete coloring , list coloring , graph power , line graph , archaeology , history

We consider a multicolored version of a problem that was originally proposed by Erdős and Rothschild. For positive integers n and r, we look for n-vertex graphs that admit the maximum number of r-edge-colorings with no copy of a triangle where exactly two colors appear. It turns out that for 2 ≤ r ≤ 12 colors and n sufficiently large, the complete bipartite graph on n vertices with balanced bipartition (the n-vertex Turan graph for the triangle) yields the largest number of such colorings, and this graph is unique with this property.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research