Loose edge-connection of graphs

DOI10.1007/S00373-023-02669-1MaRDI QIDQ6166663zbMATH OpenFDO

Authors Christoph Brause, Stanislav Jendroľ, Ingo Schiermeyer

Publication date 3 August 2023

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2206.11604

zbMATH Keywords

2-connected graphsedge colouringloose edge-connectiontrees

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: In the last years, connection concepts such as rainbow connection and proper connection appeared in graph theory and obtained a lot of attention. In this paper, we investigate the loose edge-connection of graphs. A connected edge-coloured graph $G$ is loose edge-connected if between any two of its vertices there is a path of length one, or a bi-coloured path of length two, or a path of length at least three with at least three colours used on its edges. The minimum number of colours, used in a loose edge-colouring of $G$, is called the loose edge-connection number and denoted $lec(G)$. We determine the precise value of this parameter for any simple graph $G$ of diameter at least 3. We show that deciding, whether $lec(G)=2$ for graphs $G$ of diameter 2, is an NP-complete problem. Furthermore, we characterize all complete bipartite graphs $K_{r,s}$ with $lec(K_{r,s})=2$.

Recommendations

• Rainbow connection in graphs
• Rainbow connection and forbidden subgraphs
• Rainbow connection in sparse graphs
• Proper connection number 2, connectivity, and forbidden subgraphs
• scientific article; zbMATH DE number 6837036

Cites work

• Characterizing forbidden pairs for rainbow connection in graphs with minimum degree 2
• Conflict-free connections of graphs
• Edge looseness of plane graphs
• Facially-constrained colorings of plane graphs: a survey
• From colourful to rainbow paths in graphs: colouring the vertices
• Graphs with rainbow connection number two
• Hardness and algorithms for rainbow connection
• Looseness ranges of triangulations on closed surfaces
• Odd connection and odd vertex-connection of graphs
• On forbidden subgraphs and rainbow connection in graphs with minimum degree 2
• On rainbow connection
• Proper connection and size of graphs
• Proper connection of graphs
• Rainbow connection and forbidden subgraphs
• Rainbow connection in graphs
• Rainbow connection number and connected dominating sets

Cited in

(2)

• Looseness of plane graphs
• Strongly proper connected coloring of graphs

This page was built for publication: Loose edge-connection of graphs

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