Premium
On the inclusion chromatic index of a graph
Author(s) -
Przybyło Jakub,
Kwaśny Jakub
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22636
Subject(s) - mathematics , combinatorics , conjecture , bipartite graph , edge coloring , foster graph , degree (music) , discrete mathematics , vertex (graph theory) , graph , critical graph , chromatic scale , line graph , graph power , physics , acoustics
Let χ ′ ⊂ ( G ) be the least number of colours necessary to properly colour the edges of a graph G with minimum degree δ ≥ 2 so that the set of colours incident with any vertex is not contained in a set of colours incident to any of its neighbours. We provide an infinite family of examples of graphs G with χ ′ ⊂ ( G ) ≥ ( 1 + 1 δ − 1) Δ , where Δ is the maximum degree of G , and we conjecture that χ ′ ⊂ ( G ) ≤ ⌈ ( 1 + 1 δ − 1) Δ ⌉for every connected graph with δ ≥ 2 which is not isomorphic to C 5 . The equality here is attained, for example, for the family of complete bipartite graphs. Using a probabilistic argument we support this conjecture by proving that χ ′ ⊂ ( G ) ≤ ( 1 + 4 δ ) Δ ( 1 + o ( 1 ) )(for Δ → ∞ ) for any fixed δ ≥ 2 , which implies that χ ′ ⊂ ( G ) ≤ ( 1 + 4 δ − 1) Δ for Δ large enough.