Color-line and proper color-line graphs

DOI10.1016/J.DAM.2019.06.002MaRDI QIDQ2174556zbMATH OpenOpenAlexFDO

Authors Van Bang Le, Florian Pfender

Publication date 21 April 2020

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

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

zbMATH Keywords

color-line graphgraph classline graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Motivated by investigations of rainbow matchings in edge colored graphs, we introduce the notion of color-line graphs that generalizes the classical concept of line graphs in a natural way. Let $H$ be a (properly) edge-colored graph. The (proper) color-line graph $C!L(H)$ of $H$ has edges of $H$ as vertices, and two edges of $H$ are adjacent in $C!L(H)$ if they are incident in $H$ or have the same color. We give Krausz-type characterizations for (proper) color-line graphs, and point out that, for any fixed $kge2$, recognizing if a graph is the color-line graph of some graph $H$ in which the edges are colored with at most $k$ colors is NP-complete. In contrast, we show that, for any fixed $k$, recognizing color-line graphs of properly edge colored graphs $H$ with at most $k$ colors is polynomially. Moreover, we give a good characterization for proper $2$-color line graphs that yields a linear time recognition algorithm in this case.

Recommendations

• Coloring quasi-line graphs
• On perfect colorings of line graphs
• Edge colouring line graphs of unicyclic graphs
• \((p,k)\)-coloring problems in line graphs
• Rainbow connection numbers of line graphs.

Cites work

• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• A generalization of line graphs: (X, Y)-intersection graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Complexity results for rainbow matchings
• Congruent Graphs and the Connectivity of Graphs
• scientific article; zbMATH DE number 3675952 (Why is no real title available?)
• scientific article; zbMATH DE number 1161249 (Why is no real title available?)
• scientific article; zbMATH DE number 3102314 (Why is no real title available?)
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• The interchange graph of a finite graph
• The recognition problem for line bigraphs
• The strong perfect graph theorem

Cited in

(2)

• Edge colouring line graphs of unicyclic graphs
• Well-hued graphs

This page was built for publication: Color-line and proper color-line graphs

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