On forbidden subgraphs and rainbow connection in graphs with minimum degree 2

DOI10.1016/j.disc.2014.10.006zbMath1305.05150MaRDI QIDQ482191

Zdeněk Ryjáček, Přemysl Holub, Ingo Schiermeyer

Publication date: 19 December 2014

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

Full work available at URL: https://doi.org/10.1016/j.disc.2014.10.006

zbMATH Keywords

edge coloringrainbow connectionforbidden subgraph

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C15: Coloring of graphs and hypergraphs

05C40: Connectivity

05C07: Vertex degrees

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

Loose edge-connection of graphs, Characterizing forbidden pairs for rainbow connection in graphs with minimum degree 2, On total rainbow \(k\)-connected graphs, Odd connection and odd vertex-connection of graphs, From colourful to rainbow paths in graphs: colouring the vertices

Cites Work

• Unnamed Item
• The rainbow connection number of 2-connected graphs
• Hardness and algorithms for rainbow connection
• Rainbow connection number and radius
• On rainbow connection
• Dominating cliques in \(P_ 5\)-free graphs
• Rainbow connections of graphs: a survey
• Rainbow connection number of dense graphs
• Rainbow connection number and connected dominating sets
• Graphs with rainbow connection number two
• Rainbow connection in graphs
• Rainbow Connection in Graphs with Minimum Degree Three
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree