Online coloring and L(2,1)-labeling of unit disk intersection graphs

DOI10.1137/16M1097821zbMATH Open1395.68341OpenAlexW2808443712WikidataQ62595888 ScholiaQ62595888MaRDI QIDQ4568089FDOQ4568089

Authors: Konstanty Junosza-Szaniawski, Paweł Rzążewski, Joanna Sokół, Krzysztof Węsek 

Publication date: 15 June 2018

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

Full work available at URL: https://doi.org/10.1137/16m1097821

Recommendations

• On-line coloring of geometric intersection graphs
• \( L ( 2 , 1 )\)-labeling of disk intersection graphs
• A 116/13-approximation algorithm for \(L(2,1)\)-labeling of unit disk graphs
• Independence and Coloring Problems on Intersection Graphs of Disks
• Structural Information and Communication Complexity

zbMATH Keywords

online algorithmscoloring\(L(2,1)\)-labelingunit disk intersection graphs

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Topics in Intersection Graph Theory
• Title not available (Why is that?)
• Unit disk graphs
• Unit disk graph recognition is NP-hard
• On coloring unit disk graphs
• \(T\)-colorings of graphs: recent results and open problems
• Title not available (Why is that?)
• Labelling Graphs with a Condition at Distance 2
• \(\varepsilon\)-unit distance graphs
• Fractional and \(j\)-fold coloring of the plane
• Graph labeling and radio channel assignment
• Approximations for  -Colorings of Graphs
• The $L(2,1)$-Labeling Problem on Graphs
• The \(L(2,1)\)-labeling of \(K_{1,n}\)-free graphs and its applications
• On the \(L(p,1)\)-labelling of graphs
• A Theorem about the Channel Assignment Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• On distance constrained labeling of disk graphs
• Title not available (Why is that?)
• Chromatic number of the plane \& its relatives, history, problems and results: an essay in 11 parts

Cited In (11)

• A tight bound for online colouring of disk graphs
• Title not available (Why is that?)
• On the universality and extremality of graphs with a distance constrained colouring
• Title not available (Why is that?)
• Online coloring of disk graphs
• Online coloring of short intervals
• \( L ( 2 , 1 )\)-labeling of disk intersection graphs
• Structural Information and Communication Complexity
• On distance constrained labeling of disk graphs
• Online coloring a token graph
• Online \(L(2,1)\)-coloring problem on paths with restricted size of memory

This page was built for publication: Online coloring and \(L(2,1)\)-labeling of unit disk intersection graphs

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